本文主要是介绍leetcode题：926. 将字符串翻转到单调递增（中等），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、题目描述：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'来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/flip-string-to-monotone-increasing
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
二、解题思路
方法一。定义两个数组，数组dp0[i]表示找到从左边遍历到当前点需要将1全部转为0的个数dp0[i] = dp[i-1] +1(if S[i] == '1'),else dp0[i] = dp0[i-1]。数组dp1[i]从右遍历到当前点需要将0转为1的个数，计算方式同理。然后遍历计算每个点i（0<=i<S.size())，找出dp0[i] + dp1[i]的最小值。
方法二、动态规划
也是定义两个数组。数组0表示当前点为0需要转换的个数，数组1表示当前点未1需要转换的个数。从左到右遍历，如果S==‘0’，则dp0[i] = dp0[i-1],dp1[i] = dp1[i-1]+1。如果S==‘1’,则dp0[i] = dp0[i-1]+1,dp1[i] = dp[i-1],当dp0[i-1] < dp1[i]的时候dp[1] = dp0[i-1] （这里是重点，因为题目条件里1必须在0后面，所以前面是0的话，这里可以开始变成1.=，但是S==‘0’的条件下，由于前面是1，不能转回0了，所以前面S=='0'没有这个公式）
遍历完数组，判断min(dp0[n-1],dp1[n-1]) ，n为字符串长度，取最小值。
三、代码
方法一
def minFlipsMonoIncr(self, S: str) -> int:# 基本思路是遍历所有分隔点找最小值l, r, _sum = [0], [0], 0for i in S:if i == '1':_sum += 1l.append(_sum) # 将左边全翻转为0需要的翻转次数_sum = 0for i in reversed(S):if i == '0':_sum += 1r.append(_sum) # 将右边全翻转为1需要的翻转次数r.reverse()return min(l[i]+r[i] for i in range(len(l)))方法二、
class Solution {
public:int minFlipsMonoIncr(string S) {int len = S.size();vector<vector<int>> dp(2,vector<int>(len,0));int i = 0;while(i< len && S[i] == '0')i++;if(i == len)return 0;for(;i <len; i++){if(S[i] == '1'){if(i == 0){dp[1][0] = 0;dp[0][0] = 1;continue;}dp[1][i] = dp[1][i-1];dp[0][i] = dp[0][i-1] + 1;if(dp[1][i] > dp[0][i-1])dp[1][i] = dp[0][i-1];}if(S[i] == '0'){if(i == 0){dp[0][0] = 0;dp[1][0] = 1;continue;}dp[0][i] = dp[0][i-1];dp[1][i] = dp[1][i-1] + 1;}}//print(dp);return min(dp[0][len-1],dp[1][len-1]);}void print(vector<vector<int>> & dp){for(int i = 0; i < dp.size();i++){for(int j = 0; j < dp[i].size();j++){cout<<dp[i][j]<<",";}cout<<endl;}}
};
这篇关于leetcode题：926. 将字符串翻转到单调递增（中等）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
