926. Flip String to Monotone Increasing（python+cpp）-白红宇

926. Flip String to Monotone Increasing（python+cpp）

阅读量：3703 次

发布时间：2019-05-21

本文共 1710 字，大约阅读时间需要 5 分钟。

题目：

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.
Example 1:
Input: "00110" Output: 1 Explanation: We flip the last digit to get 00111.
Example 2:
Input: "010110" Output: 2 Explanation: We flip to get 011111, or alternatively 000111.
Example 3:
Input: "00011000" Output: 2 Explanation: We flip to get 00000000.
Note:
1 <= S.length <= 20000
S only consists of '0' and '1' characters.

解释：

可以是把0翻转成1，也可以是把1翻转成0。

其实是个动态规划问题。

详细说明：

1.当遍历到'1'时，不需要翻转，因为'1'本身就应该在字符串的尾巴处

2.当遍历到'0'时，我们有两种选择：

　a.在原字符串经过flipCount翻转之后，把新加入的 '0' flip为'1'，所以需要flipCount++

　b.不翻转此处的'0'，那么它前面的'1'都需要变成'0'，它前面的'1'的个数是oneCount，所以需要翻转原字符串中的oneCount个'1'为'0'（也就是说，如果决定了遇到'1'不进行翻转，那么前面无论怎么翻转的都不管了，只需要把前面的所有的'1'翻转为'0'即可）。因此，动态规划在’0‘的情况下结果是min(flipCount + 1, oneCount)这个结果就是新的flipCount

pythond代码：

class Solution:    def minFlipsMonoIncr(self, S):        """        :type S: str        :rtype: int        """        oneCount=0        flipCount=0        for letter in S:            if letter=='1':                oneCount+=1            #遇到0的情况，要么翻转这个0，flipCount++，要么翻转之前所有的1            else:                flipCount=min(flipCount+1,oneCount)        return flipCount

c++代码：

class Solution {
   public:    int minFlipsMonoIncr(string S) {
           int flipCount=0,oneCount=0;        for(auto letter:S)        {
               if (letter=='1')                oneCount++;            else                flipCount=min(flipCount+1,oneCount);        }        return flipCount;    }};

总结：

转载地址：http://irlcn.baihongyu.com/

你可能感兴趣的文章