题目
题目:1653. 使字符串平衡的最少删除次数 - 力扣(LeetCode)
思路
1、贪心+前缀和
遍历每个字母间隔,对于每一个间隔,有:
- 删除左侧的所有’b’,删除右侧的所有’a’
取删除数最小的间隔
2、动态规划
定义 dp[i]为前 i 个字符中的最小删除数, 有状态转移方程
其中一维数组 dp 可压缩
代码:
题目:1653. 使字符串平衡的最少删除次数 - 力扣(LeetCode)
遍历每个字母间隔,对于每一个间隔,有:
取删除数最小的间隔
定义 dp[i]为前 i 个字符中的最小删除数, 有状态转移方程
dp[i]={dp[i−1],min(dp[i−1]+1,count(′b′))s[i]==’b’s[i]==’a’其中一维数组 dp 可压缩
代码:
2024年9月28日 14:48
2024年9月28日 13:00
2021年11月07日 20:08
2021年11月07日 17:03