[2022-06-11]962. 将字符串翻转到单调递增👋字符串👋动态规划

[webVueBlog]

题目链接: https://leetcode-cn.com/problems/flip-string-to-monotone-increasing

难度: Medium
标签: 字符串 动态规划

[dreamjean]

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

Description

Difficulty: 中等

Related Topics: 字符串, 动态规划

如果一个二进制字符串，是以一些 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 <= 10⁵
• s[i] 为 '0' 或 '1'

Solution

思路：

• 遍历 s:
  • 如果为 1: 统计目前为止遇到的所有的 1
  • 如果为 0, 可以选择翻转或不翻转：
    • 不翻转： 保持不变，只需要知道到目前为止的计数
    • 翻转为 1： 在原有的结果上加 1
• 要维持翻转后的单调递增，只需要比较 0 翻转前后的值，取最小值

Language: JavaScript

/**
 * @param {string} s
 * @return {number}
 */
var minFlipsMonoIncr = function(s) {
    let [res, cntOnes] = [0, 0];

    for (let i = 0; i < s.length; i++) {
        s[i] === '1' ? cntOnes++ : res = Math.min(res + 1, cntOnes);
    }

    return res;
};