LeetCode 926. 将字符串翻转到单调递增
题目描述
题意分析
每次可以把一个
0翻为1，或把一个1翻为0。目标字符串必须是若干个0后接若干个1，其中任意一段都可以为空，所以全零、全一也合法；要求的是最少翻转次数。
解法：DP（结尾为 0/1 的最少翻转）
核心思路
[!blue]
扫描到某个位置后，用
dp0表示把当前前缀变成合法且末位为0的最小代价，用dp1表示变成合法且末位为1的最小代价。合法字符串一旦出现1就不能再出现0，所以dp0对应的前缀实际上必须全为零。设当前原字符为
c。如果把它作为末位0，前面的前缀也只能处于dp0，新代价为旧dp0 + (c=='1' ? 1 : 0)。如果把它作为末位1，前面既可以全零，也可以已经以一结尾，因此新代价为min(旧dp0,旧dp1) + (c=='0' ? 1 : 0)。这两种转移列出了合法末位的全部前驱，没有允许
1后接0；对每种末位选择最便宜的前驱，就得到该状态的最小代价。依次处理所有字符后，两种状态覆盖了全部合法终态，答案取它们的较小值。两个初值都设为零，是给首字符提供同一个空前缀的零代价，并不表示空串真的有某个末位。每轮计算必须使用旧状态：先用临时变量保存新
dp1，再更新dp0，最后写回dp1，避免把当前字符重复计入前驱代价。
解题步骤
- 空前缀的两个基础代价均设为零。
- 新 dp1 取旧两状态较小值，并在当前为零时加一。
- dp0 在当前为一时加一。
- 保存新 dp1，最终返回两状态较小值。
已经单调、全部为零或全部为一的字符串，都能沿着无需翻转的转移得到零代价。不能只返回
dp1，否则会强迫合法的全零结果出现一个1。
代码实现
class Solution {
public int minFlipsMonoIncr(String s) {
int dp0 = 0;
int dp1 = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
// 一结尾可接两种旧状态，先保存结果以免旧的零结尾状态被覆盖。
int newDp1 = Math.min(dp0, dp1) + (c == '0' ? 1 : 0);
dp0 = dp0 + (c == '1' ? 1 : 0);
dp1 = newDp1;
}
return Math.min(dp0, dp1);
}
}
func minFlipsMonoIncr(s string) int {
dp0, dp1 := 0, 0
for i := 0; i < len(s); i++ {
c := s[i]
// 一结尾可接两种旧状态，先保存结果以免旧的零结尾状态被覆盖。
newDp1 := min(dp0, dp1)
if c == '0' {
newDp1++
}
if c == '1' {
dp0++
}
dp1 = newDp1
}
return min(dp0, dp1)
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
复杂度分析
- 时间复杂度：$O(n)$，每个字符只更新两个状态。
- 空间复杂度：$O(1)$，两个状态与临时值。
关键点总结
[!green]
- 零结尾只能来自零结尾，一结尾可以来自两种状态。
- 单调允许重复零或一，不是严格递增。
- 全零也是合法终态，不能只返回 dp1。
易错点总结
[!yellow]
dp0不能从dp1转移，否则会接受一后面再次出现零。- 先更新
dp0再计算新dp1，可能重复计算当前字符的代价。- 翻转有两个方向，不能预先限定只把零变一或只把一变零。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1653. 使字符串平衡的最少删除次数 | 中等 | 同样让两类字符按先后顺序排列，原题通过删除修正，本题通过翻转修正。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！