『LeetCode』926 将字符串翻转到单调递增

题目

926. 将字符串翻转到单调递增

如果一个二进制字符串，是以一些 0（可能没有 0）后面跟着一些 1（也可能没有 1）的形式组成的，那么该字符串是 单调递增的。

给你一个二进制字符串 s，你可以将任何 0 翻转为 1 或者将 1 翻转为 0 。

返回使 s 单调递增的最小翻转次数。

示例 1：

输入：s = "00110"
输出：1
解释：翻转最后一位得到 00111.

示例 2：

输入：s = "010110"
输出：2
解释：翻转得到 011111，或者是 000111。

示例 3：

输入：s = "00011000"
输出：2
解释：翻转得到 00000000。

提示：

$1 <= s.length <= 10^{5}$
$s[i]$ 为 $'0'$ 或 $'1'$

题解

【将字符串翻转到单调递增】动态规划

动态规划

实际上题目要求我们将字符串变为 0...01...1 的形式所需的最小从操作次数所以关键在于 0, 1 转折点在那个位置比较合适。

最简单的办法就是枚举转折点，没有 0, 只有一个 0, ..., 然后遍历字符串计算，但这种做法是 $O(n^2)$ 复杂度的，对于 $10^5$ 范围的题目而言显然是无法接受的，这要求我们找到一个更高效的方法。

通过仔细观察，其实我们是有可能做到 $O(1)$ 时间进行转换的，考虑原问题的一个子问题，给出一个子字符串，已知其最小操作次数，在子字符串后面再添加一个字符，如何得到新字符串的最小操作次数，这里其实有 4 种情况：

子字符串以 1 结尾，那么新加的字符必须是 1，如果为 0 则必须操作一次将其变为 1
子字符串以 0 结尾，新加字符是 1，此时有两种选择
- 可以把当前位置作为 01 之间的转折点，不增加操作次数
- 或者将 1 转为 0，操作次数 +1
子字符串以 0 结尾，新加字符是 0, 无需操作

由此我们得到了由子问题向原问题转移的方法，用 $dp[i][j]$ 表示以 $j$ 结尾的长度为 $i$ 的子字符串的最小操作次数，那么数学表达为：

$$ \[\begin{aligned} dp[i][0] &= \begin{cases} dp[i- 1][0], & s[i] = 0 \\ dp[i - 1][0] + 1, & s[i] = 1 \end{cases} \\ dp[i][1] &= \begin{cases} dp[i- 1][1] + 1, & s[i] = 0 \\ \min (dp[i - 1][0], dp[i - 1][1]), & s[i] = 1 \end{cases} \\ \end{aligned}\]

更加一步，由于每次转移都只与上一次的状态有关，所以可以使用滚动数组的方法优化空间，并且只有两种状态，所以可以更进一步只用两个变量表达即可。

# Code language: Python
class Solution:
    def minFlipsMonoIncr(self, s: str) -> int:
        # 最后一位是 0, 1 的最小翻转次数
        zero, one = 0, 0
        for c in s:
            if c == '0':
                one += 1
            else:
                one = min(zero, one)
                zero += 1
        return min(zero, one)

// Code language: Java
class Solution {
    public int minFlipsMonoIncr(String s) {
        int zero = 0, one = 0;
        for (char c: s.toCharArray()) {
            if (c == '0') one++;
            else one = Math.min(zero++, one);
        }
        return Math.min(zero, one);
    }
}

// Code language: C++
class Solution {
public:
    int minFlipsMonoIncr(string s) {
        int zero = 0, one = 0;
        for (char c: s) {
            if (c == '0') one++;
            else one = min(zero++, one);
        }
        return min(zero, one);
    }
};

时间复杂度: $O(n)$
空间复杂度: $O(1)$

如果对你有帮助的话，请给我点个赞吧~

欢迎前往我的博客或 Algorithm - Github 查看更多题解

小鲸鱼的梦境

『LeetCode』926 将字符串翻转到单调递增

题目

标签

题解

动态规划