青海省住房和城乡建设厅 网站首页,wordpress媒体库图片,怎么制作网站vi页面,如何制作一个电脑软件给你一个字符串 s #xff0c;它仅包含字符 a 和 b 。你可以删除 s 中任意数目的字符#xff0c;使得 s 平衡 。当不存在下标对 (i,j) 满足 i j #xff0c;且 s[i] b 的同时 s[j] a #xff0c;此时认为 s 是 平衡 的。请你返回使 s 平衡 的 最少 删除次数。…给你一个字符串 s 它仅包含字符 a 和 b 。你可以删除 s 中任意数目的字符使得 s 平衡 。当不存在下标对 (i,j) 满足 i j 且 s[i] b 的同时 s[j] a 此时认为 s 是 平衡 的。请你返回使 s 平衡 的 最少 删除次数。 示例 1输入s aababbab输出2解释你可以选择以下任意一种方案下标从 0 开始删除第 2 和第 6 个字符aababbab - aaabbb下标从 0 开始删除第 3 和第 6 个字符aababbab - aabbbb。示例 2输入s bbaaaaabb输出2解释唯一的最优解是删除最前面两个字符。 提示1 s.length 105s[i] 要么是 a 要么是 b 。来源力扣LeetCode链接https://leetcode.cn/problems/minimum-deletions-to-make-string-balanced著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。我觉得这是一道挺典型的前缀和的题目但是是假前缀和-如果你想节省空间的话不用全记。首先思考人类是怎么做这道题的。枚举吗枚举什么前a后b枚举的是断点。假设我们确定了断点是i这个位置假设[0,i-1]是a[i,end]是b怎么计算要删除多少[0,i-1]中b的个数[i,end]中a的个数。那每次统计i点需要删除多少的时候需要重新统计a和b的个数吗不需要只需要根据当前的数决定谁加谁减就可以了。b是正序前缀和a是逆序前缀和。class Solution {
public:int minimumDeletions(string s) {int ls.length();if(l1){return 0;}int conta0;int contb0;if(s[l-1]a){conta1;}if(s[0]b){contb1;}for(int il-2;i0;--i){if(s[i]a){conta;} }int contconta;if(s[0]a){conta--;}for(int i1;il;i){contmin(cont,contacontb);if(s[i]b){contb;}else{conta--;}}contmin(cont,contb);return cont;}
};但是感觉两次循环还是得有的毕竟方向不一样。动态规划的方法是我最开始的思路但是我想不通也写不出来现在还没看懂谁给我仔细讲讲。。。
