Tag
【貪心】【字符串】【2024-01-13】
題目來源
2182. 構(gòu)造限制重復(fù)的字符串
解題思路
方法一：貪心
思路
解題思想比較簡單，利用貪心思想，每次選擇當(dāng)前剩余字符串中字典序最大的字符加到答案字符串末尾，如果答案字符串末尾的字符已經(jīng)連續(xù)出現(xiàn)了 repeatLimit 次，則將字典序次大的字符加到答案字符串，隨后繼續(xù)選擇當(dāng)前剩余字符串的字典序最大的字符加到字符串末尾，直至使用完字符或沒有新的字符可以合法加入。
想法比較簡單，但實現(xiàn)起來稍微有點難度，具體實現(xiàn)見下方算法部分。
算法
const int N = 26;
class Solution {
public:
string repeatLimitedString(string s, int repeatLimit) {
vector<int> count(N);
// 統(tǒng)計每個字符出現(xiàn)次數(shù)
for (char c : s) {
count[c - 'a']++;
}
string ret;
int m = 0;
for (int i = N - 1, j = N - 2; i >= 0 && j >= 0;) {
// 當(dāng)前字符已經(jīng)填完，填入后面的字符，重置 m
if (count[i] == 0) {
m = 0;
i--;
}
// 當(dāng)前字符未超過限制
else if (m < repeatLimit) {
count[i]--;
ret.push_back('a' + i);
m++;
}
// 當(dāng)前字符已經(jīng)超過限制，查找可填入的其他字符
else if (j >= i || count[j] == 0) {
j--;
}
// 當(dāng)前字符已經(jīng)超過限制，填入其他字符，并且重置 m
else {
count[j]--;
ret.push_back('a' + j);
m = 0;
}
}
return ret;
}
};
復(fù)雜度分析
時間復(fù)雜度：
O
(
n
+
∑
)
O(n+ \sum)
O(n+∑)，
n
n
n 為字符串 s 的長度，
∑
=
26
\sum = 26
∑=26 為小寫字符集的長度。
空間復(fù)雜度： O ( ∑ ) O(\sum) O(∑)。
寫在最后
如果您發(fā)現(xiàn)文章有任何錯誤或者對文章有任何疑問，歡迎私信博主或者在評論區(qū)指出 ??????。
如果大家有更優(yōu)的時間、空間復(fù)雜度的方法，歡迎評論區(qū)交流。文章來源：http://www.zghlxwxcb.cn/news/detail-813324.html
最后，感謝您的閱讀，如果有所收獲的話可以給我點一個 ?? 哦。文章來源地址http://www.zghlxwxcb.cn/news/detail-813324.html
到了這里，關(guān)于【每日一題】構(gòu)造限制重復(fù)的字符串的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
