926-将字符串翻转到单调递增（Flip String to Monotone Increasing）

傷城~ 2022-01-21 05:57 108阅读 0赞

**题目描述**  
**中文**

如果一个由 '0' 和 '1' 组成的字符串，是以一些 '0'（可能没有 '0'）后面跟着一些 '1'（也可能没有 '1'）的形式组成的，
    那么该字符串是单调递增的。
    
    我们给出一个由字符 '0' 和 '1' 组成的字符串 S，我们可以将任何 '0' 翻转为 '1' 或者将 '1' 翻转为 '0'。
    
    返回使 S 单调递增的最小翻转次数。

**英文**

A string of '0's and '1's is monotone increasing if it consists of some number of '0's (possibly 0), 
    followed by some number of '1's (also possibly 0.)
    We are given a string S of '0's and '1's, and we may flip any '0' to a '1' or a '1' to a '0'.
    Return the minimum number of flips to make S monotone increasing.

示例 1：

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

示例 2：

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

示例 3：

输入："00011000"
    输出：2
    解释：我们翻转得到 00000000。

**解题思路**

*  这样一个递增的字符串肯定有一个点，从他开始左边全部为‘0’，右边全部为‘1’（若字符串全为1，割点位置可看为-1；若字符串全为0，割点位置可看为length(从0开始))。
 *  如此一来，我们就可以计算出每个位置，将他右边全变为1，和左边全变为0时的翻转次数，并将其存入一个数组。
 *  而我们最后的结果就是要得到翻转次数最少的，也就是**把这个位置左边全转为0加上右边全转为1的最小值**，这就是本道题的**规划方程**。

//解题思路：正向遍历一次统计需要翻转的‘1’，反向遍历统计需要翻转的‘0’
    	public int minFlipsMonoIncr(String S) {
    		int min_reverse = Integer.MAX_VALUE, left_zero = 0,right_zero = 0;	//统计正向需要翻转的1和反向需要翻转的0
    		char[] str = S.toCharArray();
    		int[] left = new int[str.length+1];		//把1转为0的数组
    		int[] right = new int[str.length + 1];	//把0转为1的数组
    		for(int i = 0; i < str.length;i++){			//统计正向全部把1转为0
    			if(str[i] == '1'){
    				left[i + 1] = ++left_zero;
    			}else{
    				left[i + 1] = left_zero;
    			}
    		}
    		for(int j = str.length - 1;j >= 0;j--){		//反向全部把0转为1
    			if(str[j] == '0'){
    				right[j] = ++right_zero;
    			}
    			else{
    				right[j] = right_zero;
    			}
    		}
    		for(int i = 0; i < left.length;i++){
    			if(min_reverse > left[i] + right[i])
    				min_reverse = left[i] + right[i];
    		}
    		return min_reverse;
        }

来源：力扣（LeetCode）  
链接：[https://leetcode-cn.com/problems/flip-string-to-monotone-increasing][https_leetcode-cn.com_problems_flip-string-to-monotone-increasing]

[https_leetcode-cn.com_problems_flip-string-to-monotone-increasing]: https://leetcode-cn.com/problems/flip-string-to-monotone-increasing