跳转至

剑指 Offer II 092. 翻转字符

题目描述

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

我们给出一个由字符 '0' 和 '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 <= 20000
  • s 中只包含字符 '0' 和 '1'

 

注意：本题与主站 926 题相同： https://leetcode.cn/problems/flip-string-to-monotone-increasing/

解法

方法一：枚举

我们先预处理得到右侧的 $0$ 的个数，记为 $right0$，初始化一个变量 $left0$，表示左侧的 $0$ 的个数。如果最终字符串变成全 '0' 或者全 '1'，那么答案为 $ans= \min(right0, n - right0)$。

接下来，我们枚举每个位置作为 '0' 和 '1' 的分界点（约定分界点为 '0'），计算出以当前位置为分界点的答案，最后取最小值即可。

时间复杂度 $O(n)$，其中 $n$ 是字符串的长度。空间复杂度 $O(1)$。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def minFlipsMonoIncr(self, s: str) -> int:
        left0, right0 = 0, s.count("0")
        n = len(s)
        ans = min(right0, n - right0)
        for i, c in enumerate(s, 1):
            x = int(c)
            right0 -= x ^ 1
            left0 += x ^ 1
            ans = min(ans, i - left0 + right0)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int minFlipsMonoIncr(String s) {
        int n = s.length();
        int left0 = 0, right0 = 0;
        for (int i = 0; i < n; ++i) {
            if (s.charAt(i) == '0') {
                ++right0;
            }
        }
        int ans = Math.min(right0, n - right0);
        for (int i = 1; i <= n; ++i) {
            int x = s.charAt(i - 1) == '0' ? 0 : 1;
            right0 -= x ^ 1;
            left0 += x ^ 1;
            ans = Math.min(ans, i - left0 + right0);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int minFlipsMonoIncr(string s) {
        int n = s.size();
        int left0 = 0, right0 = 0;
        for (char& c : s) {
            right0 += c == '0';
        }
        int ans = min(right0, n - right0);
        for (int i = 1; i <= n; ++i) {
            int x = s[i - 1] == '1';
            right0 -= x ^ 1;
            left0 += x ^ 1;
            ans = min(ans, i - left0 + right0);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
func minFlipsMonoIncr(s string) int {
    n := len(s)
    left0, right0 := 0, 0
    for _, c := range s {
        if c == '0' {
            right0++
        }
    }
    ans := min(right0, n-right0)
    for i, c := range s {
        x := 0
        if c == '1' {
            x = 1
        }
        right0 -= x ^ 1
        left0 += x ^ 1
        ans = min(ans, i+1-left0+right0)
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
function minFlipsMonoIncr(s: string): number {
    const n = s.length;
    let [left0, right0] = [0, 0];
    for (const c of s) {
        right0 += c === '0' ? 1 : 0;
    }
    let ans = Math.min(right0, n - right0);
    for (let i = 1; i <= n; ++i) {
        const x = s[i - 1] === '0' ? 0 : 1;
        right0 -= x ^ 1;
        left0 += x ^ 1;
        ans = Math.min(ans, i - left0 + right0);
    }
    return ans;
}

评论