将字符串翻转到单调递增

[编程题]将字符串翻转到单调递增

热度指数：48 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

我们给出一个由字符 '0' 和 '1' 组成的字符串 S，我们可以将任何 '0' 翻转为 '1' 或者将 '1' 翻转为 '0'。

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

示例1

输入

"00110"

输出

说明

我们翻转最后一位得到00111.

示例2

输入

"00011000"

输出

说明

我们翻转得到00000000。

算法知识视频讲解

南屏机修组扛把子

dpmk,m表示前m个字符，k表示前面以0或者1结尾。这里有嵌套子问题，当前字符翻不翻，看前面是什么字符结尾且前面字符的最小次数

发表于 2022-12-15 15:43:21 回复(0)

菲尼克斯弗兰克

import java.util.*;
public class Solution {
    // 动态规划-状态压缩
    public int minFlipsMonoIncr (String s) {
        int[] dp = new int[2];
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '0') { // 当前为0
                dp[1] = Math.min(dp[0], dp[1])+1;
            } else { // 当前为1
                int tmp = dp[0]+1;
                dp[1] = Math.min(dp[0], dp[1]);
                dp[0] = tmp;
            }
        }
        return Math.min(dp[0], dp[1]);
    }
}

发表于 2022-07-17 12:26:42 回复(0)