Leetcode5634. 删除子字符串的最大得分[C 题解]：贪心
文章目录
- 题目
- 题目链接
题目
样例
字符串可以分成很多段，[ ab的组合]、其他字母、[ab的组合]、其他字母这样很多段，样例就是 cd[b]c[bbaaabab]可以拆成ab的组合和其他字母。
对于某一段[ab的组合]，需要计数a和b的个数：分别记为A和B。比如[abbaaba]其中a的个数A=4，b的个数B=3. 这一段可以操作的数量是min(A,B)=3次，这里的每次操作消耗掉一个a和一个b。而且只要有相邻的a和b就可以操作。
这里我们假定ab的得分大于等于ba的得分，即x≥y。（可以省去一半的思考时间），那么想要得分最大，就需要 删除ab的操作尽可能多。
最多可以删除多少个ab呢?
可以贪心来做。某个位置的a，能否和b配对，取决于其后面是否有b。如果和b相邻那么自然可以配对。我们从后往前遍历，计数b的数量（相当于放在后备箱），往前扫的过程中每遇到一个a，就从后备箱拿出一个b，计数器减1.代表成功配对1个ab。如果后备箱中没有b，这个a就不能配成ab。
这样遍历完之后，最大的ab个数就确定了，而总的操作次数是min(A,B)，则操作ba的个数就是min(A,B)-ab个数.然后分别乘以得分x和y即为最大得分。
ac代码
class Solution {public: int maximumGain(string s, int x, int y) { //假定x≥y if(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 ;//执行这一步之后j一定在i后面 int a=0,b=0,c=0, remain=0;//remain表示后备箱中b的数量 //c表示找出来ab的数量 for(int k = j-1; k>= i; k --){ //具体的一段的处理 if(s[k]=='a'){ a ; if(remain) { //后备箱中还有b remain--; c ; } }else {//s[k]=='b' b ; remain ; } } res =c*x (min(a,b)-c)*y;//加号后面表示"ba"的数量×分数y i=j; //这一段结束，遍历下一段 } return res; }};题目链接
赞 (0)