力扣今日题926. 将字符串翻转到单调递增

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

思路:

动态规划，状态转移方程： 当出现0的时候，可以对0进行+1操作或使得前面的所有1变成0， 状态转移方程 ret=min(ret + 1, num_1);

class Solution {
    public int minFlipsMonoIncr(String s) {
        char[] cs = s.toCharArray();
        //先将字串串转成数组，ret是用来记录最小操作数的，num_1是用来记录1的个数的
        int n = cs.length, ret = 0 , num_1 = 0, num_0 = 0;
        // for(int i = 0;i <n; i++){
        //     if(cs[i] == '0'){
        //         //遇到0有两种操作，一个是将0加变成1，操作数+1。或者将这个0前面的1变成0，操作数取决于1的个数，也就是num_1.
               
        //         ret =  Math.min(ret+1,num_1);
        //     } else{
        //         //只要没遇到0 那就是1，所以num_1要++ ，
        //         num_1++;
        //     }
        // }

        //思路一样，这次是从后往前遍历，遇到1有两种操作，一种是将1变成0操作数+1，另一种就是将这个1之后的0全部变成一

        for(int i = n; i > 0 ; i--){
            if(cs[i-1] == '1'){
                ret = Math.min(ret + 1, num_0);
            }else{
                num_0++;
            }
        }
        return ret; 
    }
}

2022/6/11