Leetcode 926 Flip String to Monotone Increasing

发表于 |

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

我们给出一个由字符 ‘0’ 和 ‘1’ 组成的字符串 S，我们可以将任何 ‘0’ 翻转为 ‘1’ 或者将 ‘1’ 翻转为 ‘0’。

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

示例 1：
输入：”00110”
输出：1
解释：我们翻转最后一位得到 00111.

示例 2：
输入：”010110”
输出：2
解释：我们翻转得到 011111，或者是 000111。

示例 3：
输入：”00011000”
输出：2
解释：我们翻转得到 00000000。

提示：

  1. 1 <= S.length <= 20000
  2. S 中只包含字符 ‘0’ 和 ‘1’

题意分析：
将给定的字符串s中的某些字符翻转，使其变成一个以若干个0开头，紧接着若干个1结尾的字符串。
问最小的翻转次数

思路分析：
假设经过最优解的翻转使其变成了 s = '0'*i + '1'*j
其实我们要决定的是在原字符串中选择哪一个位置的’1’，使其作为最优解中的第一个’1’！

例如对于示例2中的010110，假设我们选择index=1处的’1’作为开头的’1’，那么我们需要将后面所有的’0’全部翻转成’1’，翻转次数取决于后面’0’的个数。

又假设我们选取index=3处的’1’作为开头的’1’，那么我们需要将前面所有的'1'翻转成0，将后面所有的'0'翻转成'1'，翻转次数取决于前面’1’的个数和后面’0’的个数。

OK，那我们只要一直记录着当前位置的前面有多少个1，后面有多少个0即可！
注意：可能存在最后全为0的情况（如示例3），那么我们是选不到某个’1’作为开头的，所以我们先将全部翻转成’0’所花费的次数作为初始默认次数，然后和我们每次计算的结果比较即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 68ms
class Solution(object):
    def minFlipsMonoIncr(self, s):
        n = len(s)
        cnt0 = s.count('0')
        cnt1 = 0
        res = n - cnt0
        for i in range(n):
            if s[i] == '0': 
                cnt0 -= 1
            elif s[i] == '1':
                res = min(res, cnt1+cnt0)
                cnt1 += 1
        return res