題目鏈接

題意

給你一個(gè)字符串 s 和一個(gè)整數(shù) repeatLimit ，用 s 中的字符構(gòu)造一個(gè)新字符串 repeatLimitedString ，使任何字母 連續(xù) 出現(xiàn)的次數(shù)都不超過 repeatLimit 次。你不必使用 s 中的全部字符。

返回 字典序最大的 repeatLimitedString 。

如果在字符串 a 和 b 不同的第一個(gè)位置，字符串 a 中的字母在字母表中出現(xiàn)時(shí)間比字符串 b 對(duì)應(yīng)的字母晚，則認(rèn)為字符串 a 比字符串 b 字典序更大 。如果字符串中前 min(a.length, b.length) 個(gè)字符都相同，那么較長(zhǎng)的字符串字典序更大。
提示：

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

思路

貪心的構(gòu)造

• 每次將當(dāng)前剩余的字典序最大的字符添加到答案里，如果該字符已經(jīng)連續(xù)出現(xiàn)了repeatLimit 次，則先將當(dāng)前剩余的字典序次大的字符添加到答案里，再繼續(xù)將當(dāng)前剩余的字典序最大的字符添加到答案里，直到該最大的字符用完或是沒有次大的字符可以插入

有兩種寫法

1. 多層for循環(huán)，不斷嘗試填入新字符
   • 結(jié)合上述的思路可以得知，每個(gè)字符i最多被添加min(repeatLimit,mp[i])次，其中mp[i]為字符i的出現(xiàn)次數(shù)
   • 可以先統(tǒng)計(jì)字符串s里每個(gè)字符的出現(xiàn)次數(shù)
   • 倒序進(jìn)行遍歷，這時(shí)候i里維護(hù)的就是當(dāng)前剩余的字典序最大的字符
   • 嘗試將字符i添加到答案字符串里
   • 如果i已經(jīng)填完了的話，跳出循環(huán)，找下一個(gè)當(dāng)前剩余的字典序最大的字符
   • 否則的話找第一個(gè)存在且字典序次大的字符，插入到答案字符串里，這樣后面就可以繼續(xù)填字母i
2. 使用優(yōu)先隊(duì)列維護(hù)字典序最大字符和次大字符
   • 思路1的本質(zhì)是通過for循環(huán)找當(dāng)前剩余的字典序最大/次大的字符，可以通過優(yōu)先隊(duì)列來維護(hù)

代碼

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])個(gè)字母i
				mp[i]--
				ans = append(ans, i)
			}
			if mp[i] == 0 {//i填完了 找下一個(gè)字典序最大的字母
				break
			}
			for las >= 0 && mp[las] == 0 {//找到第一個(gè)存在的字典序次大的字母
				las--
			}
			if las < 0 {//找不到 跳出
				break
			}
            //先填入次大字母 后面可以繼續(xù)填最大字母i
			mp[las]--
			ans = append(ans, las)
		}
	}
	return string(ans)
}

文章來源地址http://www.zghlxwxcb.cn/news/detail-797953.html

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;
		}
};

到了這里，關(guān)于【力扣·每日一題】2182.構(gòu)造限制重復(fù)的字符串（模擬 貪心 優(yōu)先隊(duì)列 C++ Go）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！