网站开发和软件开发哪个好,上海公司电话,wordpress 超级卡,wordpress金融模板下载文章目录 Tag题目来源解题思路方法一#xff1a;贪心空间复杂度#xff1a; O ( ∑ ) O(\sum) O(∑)。 写在最后 Tag
【贪心】【字符串】【2024-01-13】 题目来源
2182. 构造限制重复的字符串 解题思路
方法一#xff1a;贪心
思路
解题思想比较简单#xff0c;利用贪… 文章目录 Tag题目来源解题思路方法一贪心空间复杂度 O ( ∑ ) O(\sum) O(∑)。 写在最后 Tag
【贪心】【字符串】【2024-01-13】 题目来源
2182. 构造限制重复的字符串 解题思路
方法一贪心
思路
解题思想比较简单利用贪心思想每次选择当前剩余字符串中字典序最大的字符加到答案字符串末尾如果答案字符串末尾的字符已经连续出现了 repeatLimit 次则将字典序次大的字符加到答案字符串随后继续选择当前剩余字符串的字典序最大的字符加到字符串末尾直至使用完字符或没有新的字符可以合法加入。
想法比较简单但实现起来稍微有点难度具体实现见下方算法部分。
算法
const int N 26;
class Solution {
public:string repeatLimitedString(string s, int repeatLimit) {vectorint count(N);// 统计每个字符出现次数for (char c : s) {count[c - a];}string ret;int m 0;for (int i N - 1, j N - 2; i 0 j 0;) {// 当前字符已经填完填入后面的字符重置 mif (count[i] 0) { m 0;i--; } // 当前字符未超过限制else if (m repeatLimit) { count[i]--;ret.push_back(a i);m;} // 当前字符已经超过限制查找可填入的其他字符else if (j i || count[j] 0) { j--;} // 当前字符已经超过限制填入其他字符并且重置 melse { count[j]--;ret.push_back(a j);m 0;}}return ret;}
};复杂度分析
时间复杂度 O ( n ∑ ) O(n \sum) O(n∑) n n n 为字符串 s 的长度 ∑ 26 \sum 26 ∑26 为小写字符集的长度。
空间复杂度 O ( ∑ ) O(\sum) O(∑)。
写在最后
如果您发现文章有任何错误或者对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度的方法欢迎评论区交流。
最后感谢您的阅读如果有所收获的话可以给我点一个 哦。
