大悟县城乡建设局网站,天津工程建设网官方网站,福建设计院网站,微信公众号的步骤目录
题目来源
题目描述
示例
提示
题目解析
算法源码 题目来源
1653. 使字符串平衡的最少删除次数 - 力扣#xff08;LeetCode#xff09; 题目描述
给你一个字符串 s #xff0c;它仅包含字符 a 和 b 。
你可以删除 s 中任意数目的字符#xff0c;使得 …目录
题目来源
题目描述
示例
提示
题目解析
算法源码 题目来源
1653. 使字符串平衡的最少删除次数 - 力扣LeetCode 题目描述
给你一个字符串 s 它仅包含字符 a 和 b 。
你可以删除 s 中任意数目的字符使得 s 平衡 。当不存在下标对 (i,j) 满足 i j 且 s[i] b 的同时 s[j] a 此时认为 s 是 平衡 的。
请你返回使 s 平衡 的 最少 删除次数。 示例 输入s aababbab 输出2 解释你可以选择以下任意一种方案 下标从 0 开始删除第 2 和第 6 个字符aababbab - aaabbb 下标从 0 开始删除第 3 和第 6 个字符aababbab - aabbbb。 输入s bbaaaaabb 输出2 解释唯一的最优解是删除最前面两个字符。 提示
1 s.length 105s[i] 要么是 a 要么是 b 。题目解析
本题最优思路是采用动态规划。
我们可以定义一个dp数组dp[i]的含义是将输入字符串s的0~i区间变得平衡的最少修改次数而dp[i1]其实就是相当于在dp[i]的0~i区间尾部追加一个字符此时我们只需要考虑追加字符的处理来保持0~i1区间平衡即可。 如果追加的s[i] ‘b’, 则不会破坏平衡。
如果追加的s[i] a则会破坏破坏此时有两种删除策略
由于0~i-1已经平衡了因此我们可以删除s[i]已期不会破坏0~i-1已形成的平衡即dp[i] dp[i-1] 1 1对应删除s[i]的动作如果我们不删除s[i]的话则需要将 0~i-1 中所有的b删除因此在遍历s的过程中我们还需要记录 0 ~ i 范围内的b的数量比如countB[i] 含义为 0~i范围内b的数量。此时 dp[i] countB[i-1]
我们只需要取上面两个dp[i]中最小的即可即dp[i] min(dp[i-1] 1, countB[i-1]) 但是上面将dpcountB定义为数组非常浪费内存这里起始最终只要求的是输入s字符串0~n-1区间变得平衡的最小次数因此我们不需要缓存其他区间最小数次数据而是可以对dpcountB数组进行压缩每次用最新值覆盖前一个值即可。 算法源码
JS
/*** param {string} s* return {number}*/
var minimumDeletions function(s) {let dp 0 // dp记录的是将s的[0, i]区间变得平衡的最少次数let countB 0 // countB 记录的是 s 的 [0, i]区间中b字符的个数for(let i 0; i s.length; i) {if(s[i] a) dp Math.min(dp 1, countB) // 末尾新增a会破坏平衡此时需要进行删除动作else countB // 末尾新增b不会破坏平衡}return dp;
}; Java
class Solution {public int minimumDeletions(String s) {int dp 0; // dp记录的是将s的[0, i]区间变得平衡的最少次数int countB 0; // countB 记录的是 s 的 [0, i]区间中b字符的个数for(int i0; i s.length(); i) {if(s.charAt(i) a) dp Math.min(dp 1, countB); // 末尾新增a会破坏平衡此时需要进行删除动作else countB; // 末尾新增b不会破坏平衡}return dp;}
} Python
class Solution(object):def minimumDeletions(self, s):dp 0 # dp记录的是将s的[0, i]区间变得平衡的最少次数countB 0 # countB 记录的是 s 的 [0, i]区间中b字符的个数for c in s:if c a:dp min(dp 1, countB) # 末尾新增a会破坏平衡此时需要进行删除动作else:countB 1 # 末尾新增b不会破坏平衡return dp
