跳到主要内容

926.将字符串翻转到单调递增

· 阅读需 2 分钟

1、题干​

如果一个二进制字符串，是以一些 0（可能没有 0）后面跟着一些 1（也可能没有 1）的形式组成的，那么该字符串是 单调递增 的。

给你一个二进制字符串 s，你可以将任何 0 翻转为 1 或者将 1 翻转为 0 。

返回使 s 单调递增的最小翻转次数。

 

示例 1：

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

示例 2：

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

示例 3：

输入：s = "00011000"
输出：2
解释：翻转得到 00000000。

 

提示：

  • 1 <= s.length <= 105
  • s[i] 为 '0' 或 '1'

2、解题思路​

字符串中的 10 打乱了递增顺序，要保证递增性只需要将其替换成 00、01、11 中任意一种，至于替换成哪一种不重要，因为总有一个合适的，重要的是每出现1个 10 翻转次数需要加 1。

因此要求最小翻转次数，只需要循环地把所有 10 全部剔除，并累加翻转次数即可


3、代码​

var minFlipsMonoIncr = function (s) {
    let c = 0;
    while (s.indexOf('10') > -1) s = s.replace(/10/g, () => (c++, ''));
    return c;
};

4、执行结果​

image.png