题目难度: 中等

****

今天继续更新 Leetcode 的剑指 Offer（专项突击版）系列, 大家在公众号 算法精选 里回复 剑指offer2 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

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

我们给出一个由字符 '0' 和 '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 <= 20000
  • s 中只包含字符 '0' 和 '1'

题目思考

  1. 如何尽可能优化时间和空间复杂度?

解决方案

  • 分析题目, 要想使得字符串单调递增, 肯定需要在某个位置有一个虚拟的分隔符, 它左边全是 0, 右边全是 1, 分隔符在开头或末尾时则代表全 1 或全 0 的特殊情况
  • 这就引出了一个很直接的想法: 我们可以遍历每个分隔符位置, 然后统计它左边 1 的数目和右边 0 的数目, 它们的和就是需要翻转的次数, 而所有分隔符的翻转次数的最小值就是最终结果
  • 不过这样时间复杂度达到了 O(N^2), 如何优化呢?
  • 我们可以先遍历一遍字符串, 预处理统计每个下标的左边 1 和右边 0 的数目, 并记录在列表中; 然后再次遍历整个字符串, 累加两个计数, 就直接得到了每个分隔符位置的最小翻转次数, 这样就把时间复杂度优化到了 O(N), 不过需要额外的 O(N) 空间来存储两种计数, 有没有空间更优的做法呢?
  • 我们可以换个思路, 分别记录每个下标字符设为 0 或 1 时, 以它结尾的最小翻转次数, 这样我们可以根据前一下标和原始字符递推得到当前最小次数, 这就是动态规划的思想, 有以下四种情况:
    1. 当前字符是 0 且需要保持为 0 时, 则只能从上一字符设为 0 的状态转移而来, 否则就违反了单调递增条件
    2. 当前字符是 0 且需要翻转成 1 时, 则可以从上一字符设为 0 或 1 的任意状态转移而来, 并加上当前的翻转次数 1
    3. 当前字符是 1 且需要翻转成 0 时, 则只能从上一字符设为 0 的状态转移而来, 否则就违反了单调递增条件, 当然转移时也需要加上当前的翻转次数 1
    4. 当前字符是 1 且需要保持为 1 时, 则可以从上一字符设为 0 或 1 的任意状态转移而来, 无需增加翻转次数
  • 用数学语言来表示, 假设dp[i][0]/dp[i][1]分别代表将第 i 个字符设为 0/1 时的最小翻转次数, 那么就有:
    • if s[i] == '0':
      • dp[i][0]=dp[i-1][0]
      • dp[i][1]=min(dp[i-1][0],dp[i-1][1])+1
    • if s[i] == '1':
      • dp[i][0]=dp[i-1][0]+1
      • dp[i][1]=min(dp[i-1][0],dp[i-1][1])
  • 由于当前 dp 值只和前面一个 dp 值有关, 所以我们可以只使用三个变量 dp0 和 dp1, 分别代表当前字符设为 0/1 时的最小翻转次数, 从而进一步优化空间复杂度
  • 然后根据上面转移方程滚动计算新的dp0 和 dp1, 最终结果就是两个 dp 值的较小值
  • 下面的代码中有详细的注释, 方便大家理解

复杂度

  • 时间复杂度 O(N): 需要遍历整个数组一遍
  • 空间复杂度 O(1): 只需要几个常数空间的变量

代码

class Solution:
    def minFlipsMonoIncr(self, s: str) -> int:
        # 双变量滚动DP+01结尾
        # dp[i][x]表示当前以x结尾的翻转次数
        # 若s[i]==0: dp[i][0] = dp[i-1][0], dp[i][1] = min(dp[i-1][0],dp[i-1][1])+1
        # 若s[i]==1: dp[i][0] = dp[i-1][0]+1, dp[i][1] = min(dp[i-1][0],dp[i-1][1])
        # 最终结果就是min(dp[n-1])
        # dp0和dp1分别表示当前以0/1结尾时的最小翻转次数
        dp0, dp1 = 0, 0
        for c in s:
            if c == "0":
                # dp[i][0] = dp[i-1][0], 所以dp0不变
                # dp[i][1] = min(dp[i-1][0],dp[i-1][1])+1
                dp1 = min(dp0, dp1) + 1
            else:
                # dp[i][1] = min(dp[i-1][0],dp[i-1][1])
                dp1 = min(dp0, dp1)
                # dp[i][0] = dp[i-1][0]+1
                # 注意顺序, 不能先更新dp0, 否则dp1就不是从前一个dp0转移过来, 结果就不对了
                dp0 += 1
        return min(dp0, dp1)

大家可以在下面这些地方找到我~😊

我的 GitHub

我的 Leetcode

我的 CSDN

我的知乎专栏

我的头条号

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~😊

算法精选 - 微信扫一扫关注我