【力扣·每日一题】2182.构造限制重复的字符串（模拟 贪心 优先队列 C++ Go）

题目链接

题意

给你一个字符串 s 和一个整数 repeatLimit ，用 s 中的字符构造一个新字符串 repeatLimitedString ，使任何字母 连续 出现的次数都不超过 repeatLimit 次。你不必使用 s 中的全部字符。

返回 字典序最大的 repeatLimitedString 。

如果在字符串 a 和 b 不同的第一个位置，字符串 a 中的字母在字母表中出现时间比字符串 b 对应的字母晚，则认为字符串 a 比字符串 b 字典序更大 。如果字符串中前 min(a.length, b.length) 个字符都相同，那么较长的字符串字典序更大。
提示：

$1<=repeatLimit<=s.length<=10^5$
s 由小写英文字母组成

思路

贪心的构造

• 每次将当前剩余的字典序最大的字符添加到答案里，如果该字符已经连续出现了repeatLimit 次，则先将当前剩余的字典序次大的字符添加到答案里，再继续将当前剩余的字典序最大的字符添加到答案里，直到该最大的字符用完或是没有次大的字符可以插入

有两种写法

1. 多层for循环，不断尝试填入新字符
   • 结合上述的思路可以得知，每个字符i最多被添加min(repeatLimit,mp[i])次，其中mp[i]为字符i的出现次数
   • 可以先统计字符串s里每个字符的出现次数
   • 倒序进行遍历，这时候i里维护的就是当前剩余的字典序最大的字符
   • 尝试将字符i添加到答案字符串里
   • 如果i已经填完了的话，跳出循环，找下一个当前剩余的字典序最大的字符
   • 否则的话找第一个存在且字典序次大的字符，插入到答案字符串里，这样后面就可以继续填字母i
2. 使用优先队列维护字典序最大字符和次大字符
   • 思路1的本质是通过for循环找当前剩余的字典序最大/次大的字符，可以通过优先队列来维护

代码

func repeatLimitedString(s string, repeatLimit int) string {
mp := make(map[rune]int, 26)
for _, ch := range s {
mp[ch]++
}
ans := make([]rune,0,len(s))
for i := 'z'; i >= 'a'; i-- {//倒序填入字母
las := i - 1//记录次小的字母值
for {
for j := 0; j < repeatLimit && mp[i] > 0; j++ {//最多填入min(repeatLimit,mp[i])个字母i
mp[i]--
ans = append(ans, i)
}
if mp[i] == 0 {//i填完了 找下一个字典序最大的字母
break
}
for las >= 0 && mp[las] == 0 {//找到第一个存在的字典序次大的字母
las--
}
if las < 0 {//找不到 跳出
break
}
            //先填入次大字母 后面可以继续填最大字母i
mp[las]--
ans = append(ans, las)
}
}
return string(ans)
}

class Solution {
public:
string repeatLimitedString(string s, int repeatLimit) {
int mp[26];
for(int i=0; i<26; i++) {
mp[i]=0;
}
for(char ch:s) {
mp[ch-'a']++;
}
string ans;
for(int i=25; i>=0; i--) {
int las = i-1;
while(1) {
for(int j=0; j<repeatLimit&&mp[i]>0; j++) {
mp[i]--;
                        ans.push_back(i+'a');
                    //ans = ans + char(i+'a');
}
if(mp[i]==0) {
break;
}
while(las>=0&&mp[las]==0) {
las--;
}
if(las < 0) {
break;
}
mp[las]--;
                    ans.push_back(las+'a');
                //ans = ans + char(las+'a');
}
}
return ans;
}
};

原文地址：https://blog.csdn.net/weixin_45675097/article/details/135564959

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！