926. Flip String to Monotone Increasing

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. 1 <= S.length <= 20000
  2. S only consists of '0' and '1' characters.

这道题给了我们一个只有0和1的字符串,现在说是可以将任意位置的数翻转,即0变为1,或者1变为0,让组成一个单调递增的序列,即0必须都在1的前面,博主刚开始想的策略比较直接,就是使用双指针分别指向开头和结尾,开头的指针先跳过连续的0,末尾的指针向前跳过连续的1,然后在中间的位置分别记录0和1的个数,返回其中较小的那个。这种思路乍看上去没什么问题,但是实际上是有问题的,比如对于这个例子 “10011111110010111011”,如果按这种思路的话,就应该将所有的0变为1,从而返回6,但实际上更优的解法是将第一个1变为0,将后4个0变为1即可,最终可以返回5,这说明了之前的解法是不正确的。这道题可以用动态规划 Dynamic Programming 来做,需要使用两个 dp 数组,其中 cnt1[i] 表示将范围是 [0, i-1] 的子串内最小的将1转为0的个数,从而形成单调字符串。同理,cnt0[j] 表示将范围是 [j, n-1] 的子串内最小的将0转为1的个数,从而形成单调字符串。这样最终在某个位置使得 cnt0[i]+cnt1[i] 最小的时候,就是变为单调串的最优解,这样就可以完美的解决上面的例子,子串 “100” 的最优解是将1变为0,而后面的 “11111110010111011” 的最优解是将4个0变为1,总共加起来就是5,参见代码如下:
解法一:

class Solution {
public:
    int minFlipsMonoIncr(string S) {
        int n = S.size(), res = INT_MAX;
        vector<int> cnt1(n + 1), cnt0(n + 1);
        for (int i = 1, j = n - 1; j >= 0; ++i, --j) {
            cnt1[i] += cnt1[i - 1] + (S[i - 1] == '0' ? 0 : 1);
            cnt0[j] += cnt0[j + 1] + (S[j] == '1' ? 0 : 1);
        }
        for (int i = 0; i <= n; ++i) res = min(res, cnt1[i] + cnt0[i]);
        return res;
    }
};

我们可以进一步优化一下空间复杂度,用一个变量 cnt1 来记录当前位置时1出现的次数,同时 res 表示使到当前位置的子串变为单调串的翻转次数,用来记录0的个数,因为遇到0就翻1一定可以组成单调串,但不一定是最优解,每次都要和 cnt1 比较以下,若 cnt1 较小,就将 res 更新为 cnt1,此时保证了到当前位置的子串变为单调串的翻转次数最少,并不关心到底是把0变为1,还是1变为0了,其实核心思想跟上面的解法很相近,参见代码如下:
解法二:

class Solution {
public:
    int minFlipsMonoIncr(string S) {
        int n = S.size(), res = 0, cnt1 = 0;
        for (int i = 0; i < n; ++i) {
            (S[i] == '0') ? ++res : ++cnt1;
            res = min(res, cnt1);
        }
        return res;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/926

参考资料:

https://leetcode.com/problems/flip-string-to-monotone-increasing/

https://leetcode.com/problems/flip-string-to-monotone-increasing/discuss/183851/C%2B%2BJava-4-lines-O(n)-or-O(1)-DP

https://leetcode.com/problems/flip-string-to-monotone-increasing/discuss/183896/Prefix-Suffix-Java-O(N)-One-Pass-Solution-Space-O(1)

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation