每日算法系列【LeetCode 926】将字符串翻转到单调递增

题目描述

如果一个由 '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'

题解

要想把字符串变成递增的，只有两种可能，一种就是从某一处开始全是 1 ，之前都是 0 或者没有，另一种就是全 0 。那么我们只需要遍历这个 1 开始的位置就行了。

对于位置 i ，我们假设从它开始后面都是 1 ，前面都是 0 ，那么需要修改的的次数就是它后面 0 的数量减去它前面 1 的数量。

代码

c++

classSolution {
public:   
intminFlipsMonoIncr(stringS) {    
intn=S.size(); 
intdp[n+1];   
dp[n] =0;     
for (inti=n-1; i>=0; --i) {    
dp[i] =dp[i+1] + (S[i] =='1'); 
        }  
intres=dp[0]; 
for (inti=0; i<n; ++i) {    
res=min(res, dp[0]-dp[i]+n-i-dp[i]);   
        }    
returnres;
    }
};

python

classSolution:  
defminFlipsMonoIncr(self, S: str) ->int:   
n=len(S)    
dp= [0] * (n+1)    
foriinrange(n-1, -1, -1): 
dp[i] =dp[i+1] + (1ifS[i]=='1'else0)   
res=dp[0]     
foriinrange(n):   
res=min(res, dp[0]-dp[i]+n-i-dp[i])  
returnres

作者简介：godweiyang，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~