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

Categories:

题目描述
思路分析
1. 解法一：动态规划（推荐）
2. 解法二：前缀和
相似题目

题目描述

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

思路分析

解法一：动态规划（推荐）

核心思路：

定义 dp0[i] 为使 s[0..i] 单调递增且第 i 位为 '0' 所需最少翻转次数

定义 dp1[i] 为使 s[0..i] 单调递增且第 i 位为 '1' 所需最少翻转次数

转移：dp0[i] = dp0[i-1] + (s[i]=='1' ? 1 : 0)（前一位必须是 0，当前位改为 0）

转移：dp1[i] = min(dp0[i-1], dp1[i-1]) + (s[i]=='0' ? 1 : 0)（前一位可以是 0 或 1）

最终答案为 min(dp0[n-1], dp1[n-1])，并可将空间压缩至 O(1)

复杂度分析：

时间复杂度：O(n)，其中 n 为字符串长度

空间复杂度：O(1)，只保留上一步状态

class Solution {
    public int minFlipsMonoIncr(String s) {
        // dp0: 当前位为 '0' 的最少翻转次数
        // dp1: 当前位为 '1' 的最少翻转次数
        int dp0 = 0;
        int dp1 = 0;

        for (char c : s.toCharArray()) {
            // 当前位变为 '1'：前一位可以是 0 或 1，取最小值；当前是 '0' 需要翻转
            int newDp1 = Math.min(dp0, dp1) + (c == '0' ? 1 : 0);

            // 当前位变为 '0'：前一位必须是 '0'；当前是 '1' 需要翻转
            dp0 = dp0 + (c == '1' ? 1 : 0);

            dp1 = newDp1;
        }

        return Math.min(dp0, dp1);
    }
}

func minFlipsMonoIncr(s string) int {
    // dp0: 当前位为 '0' 的最少翻转次数
    // dp1: 当前位为 '1' 的最少翻转次数
    dp0, dp1 := 0, 0

    for _, c := range s {
        // 当前位变为 '1'：前一位可以是 0 或 1，取最小值
        newDp1 := min926(dp0, dp1)
        if c == '0' {
            newDp1++
        }

        // 当前位变为 '0'：前一位必须是 '0'
        if c == '1' {
            dp0++
        }

        dp1 = newDp1
    }

    return min926(dp0, dp1)
}

func min926(a, b int) int {
    if a < b {
        return a
    }
    return b
}

解法二：前缀和

核心思路：

枚举翻转分界点 i，即 s[0..i-1] 全变为 '0'，s[i..n-1] 全变为 '1'

左侧 [0, i-1] 翻转 '1' 的个数 = prefix1[i]（前缀 1 的数量）

右侧 [i, n-1] 翻转 '0' 的个数 = total0 - prefix0[i]（后缀 0 的数量）

两者之和取最小值即为答案

复杂度分析：

时间复杂度：O(n)，其中 n 为字符串长度

空间复杂度：O(n)，前缀数组

class Solution {
    public int minFlipsMonoIncr(String s) {
        int n = s.length();

        // 计算前缀 1 的数量
        int[] prefix1 = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefix1[i + 1] = prefix1[i] + (s.charAt(i) == '1' ? 1 : 0);
        }

        int total0 = 0;
        for (char c : s.toCharArray()) {
            if (c == '0') {
                total0++;
            }
        }

        int ans = Integer.MAX_VALUE;

        // 枚举分界点：左边全变 0，右边全变 1
        for (int i = 0; i <= n; i++) {
            // 左侧 [0, i-1] 中 '1' 的个数（需翻转）
            int flipLeft = prefix1[i];
            // 右侧 [i, n-1] 中 '0' 的个数（需翻转）
            int prefix0 = i - prefix1[i];
            int flipRight = total0 - prefix0;

            ans = Math.min(ans, flipLeft + flipRight);
        }

        return ans;
    }
}

func minFlipsMonoIncr(s string) int {
    n := len(s)

    // 计算前缀 1 的数量
    prefix1 := make([]int, n+1)
    for i, c := range s {
        prefix1[i+1] = prefix1[i]
        if c == '1' {
            prefix1[i+1]++
        }
    }

    total0 := 0
    for _, c := range s {
        if c == '0' {
            total0++
        }
    }

    ans := math.MaxInt32

    // 枚举分界点：左边全变 0，右边全变 1
    for i := 0; i <= n; i++ {
        // 左侧 '1' 的个数（需翻转）
        flipLeft := prefix1[i]
        // 右侧 '0' 的个数（需翻转）
        prefix0 := i - prefix1[i]
        flipRight := total0 - prefix0

        if flipLeft+flipRight < ans {
            ans = flipLeft + flipRight
        }
    }

    return ans
}

相似题目

题目	难度	考察点
121. 买卖股票的最佳时机	简单	动态规划
309. 买卖股票的最佳时机含冷冻期	中等	动态规划
1004. 最大连续1的个数 III	中等	滑动窗口
1043. 分隔数组以得到最大和	中等	动态规划
53. 最大子数组和	中等	动态规划
801. 使序列递增的最小交换次数	困难	动态规划

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/90470912