文章目錄

• • 題目
  • 題目鏈接

題目

樣例

字符串可以分成很多段，[ ab的組合]、其他字母、[ab的組合]、其他字母這樣很多段，樣例就是 cd[b]c[bbaaabab]可以拆成ab的組合和其他字母。

對于某一段[ab的組合]，需要計(jì)數(shù)a和b的個(gè)數(shù)：分別記為A和B。比如[abbaaba]其中a的個(gè)數(shù)A=4，b的個(gè)數(shù)B=3. 這一段可以操作的數(shù)量是min(A,B)=3次，這里的每次操作消耗掉一個(gè)a和一個(gè)b。而且只要有相鄰的a和b就可以操作。

這里我們假定ab的得分大于等于ba的得分，即x≥y。（可以省去一半的思考時(shí)間），那么想要得分最大，就需要 刪除ab的操作盡可能多。

最多可以刪除多少個(gè)ab呢?

可以貪心來做。某個(gè)位置的a，能否和b配對，取決于其后面是否有b。如果和b相鄰那么自然可以配對。我們從后往前遍歷，計(jì)數(shù)b的數(shù)量（相當(dāng)于放在后備箱），往前掃的過程中每遇到一個(gè)a，就從后備箱拿出一個(gè)b，計(jì)數(shù)器減1.代表成功配對1個(gè)ab。如果后備箱中沒有b，這個(gè)a就不能配成ab。

這樣遍歷完之后，最大的ab個(gè)數(shù)就確定了，而總的操作次數(shù)是min(A,B)，則操作ba的個(gè)數(shù)就是min(A,B)-ab個(gè)數(shù).然后分別乘以得分x和y即為最大得分。

ac代碼

class Solution { public:int maximumGain(string s, int x, int y) {//假定x≥yif(x<y){swap(x,y);for(auto& c:s){if(c=='a') c='b';else if(c=='b') c='a';}}int res=0;for(int i=0; i< s.size();i++){ //用i和j來指明某一段[i,j)左閉右開if(s[i]!='a' && s[i]!='b') continue;int j=i;while(j<s.size() && ( s[j]=='a'|| s[j]=='b')) j++;//執(zhí)行這一步之后j一定在i后面int a=0,b=0,c=0, remain=0;//remain表示后備箱中b的數(shù)量//c表示找出來ab的數(shù)量for(int k = j-1; k>= i; k --){ //具體的一段的處理if(s[k]=='a'){a++;if(remain) { //后備箱中還有bremain--;c++;}}else {//s[k]=='b'b++;remain++;}}res+=c*x+ (min(a,b)-c)*y;//加號后面表示"ba"的數(shù)量×分?jǐn)?shù)yi=j; //這一段結(jié)束，遍歷下一段}return res;} };

題目鏈接

Leetcode5634. 刪除子字符串的最大得分

總結(jié)

以上是生活随笔為你收集整理的Leetcode5634. 删除子字符串的最大得分[C++题解]：贪心的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。