leetcode [926] 将字符串翻转到单调递增
Contact me:
Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub
如果一个由 ‘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 <= S.length <= 20000
S 中只包含字符 '0' 和 '1'
思路来自题解:
-
对于每个字符，考虑两种情况，此字符最终状态为 0 或者 为 1，然后分别记录 0 和 1 的最少翻转次数，遍历完成后取最小值即为最少翻转次数。
-
dp[i][0]，dp[i][1] 分别代表字符 S[i] 最终选择 0 和 1 的最少翻转次数， 考虑到递增，那么 dp[i][0] 只能由 dp[i-1][0] 转化而来，所以，状态转移方程如下：
-
如果 S[i] 是 ‘1’:
dp[i][0] = dp[i-1][0] + 1 # 只能从 0 转化来，翻转 ‘1’ 为 ‘0’，翻转次数加 1 dp[i][1] = min(dp[i-1][0], dp[i-1][1]) # 已经为 ‘1’，无需翻转
-
如果 S[i] 是 ‘0’:
dp[i][0] = dp[i-1][0] # 只能从 0 转化来，无需翻转 dp[i][1] = min(dp[i-1][0] + 1, dp[i-1][1] + 1) # 翻转 ‘0’ 为 ‘1’，翻转次数加 1
-
class Solution:
def minFlipsMonoIncr(self, S: str) -> int:
zero, one = 0, 0
for ss in S:
# current is 1
# set 0, prev + 1
# keep, prev is fine
if ss == '1':
zero, one = zero + 1, min(zero, one)
# current is 0
# keep, when prev 0
# set 1, prev is fine
else:
one = one + 1
return min(zero, one)