个人学做网站,高安高端网站设计公司,什么是企业文化它包括哪些内容,濮阳门户网站开发#x1f680; 算法题 #x1f680; #x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 #x1f340; #x1f332; 越难的东西,越要努力坚持#xff0c;因为它具有很高的价值#xff0c;算法就是这样✨ #x1f332; 作者简介#xff1a;硕风和炜#xff0c;… 算法题 算法刷题专栏 | 面试必备算法 | 面试高频算法 越难的东西,越要努力坚持因为它具有很高的价值算法就是这样✨ 作者简介硕风和炜CSDN-Java领域优质创作者保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享 恭喜你发现一枚宝藏博主,赶快收入囊中吧 人生如棋我愿为卒行动虽慢可谁曾见我后退一步 算法题 目录 题目链接⛲ 题目描述 求解思路实现代码运行结果⚡ 贪心 求解思路 实现代码 运行结果 共勉 题目链接
3106. 满足距离约束且字典序最小的字符串
⛲ 题目描述
给你一个字符串 s 和一个整数 k 。
定义函数 distance(s1, s2) 用于衡量两个长度为 n 的字符串 s1 和 s2 之间的距离即
字符 ‘a’ 到 ‘z’ 按 循环 顺序排列对于区间 [0, n - 1] 中的 i 计算所有「 s1[i] 和 s2[i] 之间 最小距离」的 和 。 例如distance(“ab”, “cd”) 4 且 distance(“a”, “z”) 1 。
你可以对字符串 s 执行 任意次 操作。在每次操作中可以将 s 中的一个字母 改变 为 任意 其他小写英文字母。
返回一个字符串表示在执行一些操作后你可以得到的 字典序最小 的字符串 t 且满足 distance(s, t) k 。
示例 1
输入s “zbbz”, k 3 输出“aaaz” 解释在这个例子中可以执行以下操作 将 s[0] 改为 ‘a’ s 变为 “abbz” 。 将 s[1] 改为 ‘a’ s 变为 “aabz” 。 将 s[2] 改为 ‘a’ s 变为 “aaaz” 。 “zbbz” 和 “aaaz” 之间的距离等于 k 3 。 可以证明 “aaaz” 是在任意次操作后能够得到的字典序最小的字符串。 因此答案是 “aaaz” 。 示例 2
输入s “xaxcd”, k 4 输出“aawcd” 解释在这个例子中可以执行以下操作 将 s[0] 改为 ‘a’ s 变为 “aaxcd” 。 将 s[2] 改为 ‘w’ s 变为 “aawcd” 。 “xaxcd” 和 “aawcd” 之间的距离等于 k 4 。 可以证明 “aawcd” 是在任意次操作后能够得到的字典序最小的字符串。 因此答案是 “aawcd” 。 示例 3
输入s “lol”, k 0 输出“lol” 解释在这个例子中k 0更改任何字符都会使得距离大于 0 。 因此答案是 “lol” 。
提示
1 s.length 100 0 k 2000 s 只包含小写英文字母。 求解思路实现代码运行结果 ⚡ 贪心 求解思路
我们优先把左边的字母变成 a。想把当前的字符变成 a可以把当前的位置从左边不断减一到 a从右边不断加一到 a二者取最小值得最小的操作距离返回。因为题目限制s到t的distance小于等于k所有在判断distance距离的时候如果此时distance小于等于 k当前位置减少到ak减少此时distance的距离否则如果大于当前位置直接减少k直接结束。最后返回此时的字符串。有了基本的思路接下来我们就来通过代码来实现一下的解法。 实现代码
class Solution {public String getSmallestString(String s, int k) {char[] t s.toCharArray();for (int i 0; i t.length; i) {int dis Math.min(t[i] - a, z - t[i] 1);if (dis k) {t[i] - k;break;}t[i] a;k - dis;}return new String(t);}
}运行结果 共勉
最后我想和大家分享一句一直激励我的座右铭希望可以与大家共勉
