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

通过万岁！！！

• 题目：就是给你一个二进制字符串，然后让变成前面全是0，后面全是1，问最少反转多少次。
• 基础思路：这个题可以看到是一个动态规划的问题，因为我们在任何一个位置结束，都可以得到一个相同的问题。那我们就需要构造一个dp数组。
  • 首先想到，我们要将这个位置变成0和变成1，有两种情况。所以应该是有两个数组zeroDp和oneDp。这两个数组分别存储到i位置时，变成1或者变成0的变换次数。
  • 然后就是递推公式了。首先，如果当前位置是1，并且要是变成0，则zeroDp应该等于zeroDp前面一个+1；如果保持1，则oneDp需要等于前面zeroDp和oneDp两个的最小值。如果当前位置是0，并且要保持0，zeroDp等于前一个zeroDp；如果要变成1，则oneDp等于前面zeroDp和oneDp两个的最小值+1。
  • 最后返回两个数组最后一个元素中的最小值即可。
• 进阶思路：其实我们这里没有必要用两个数组的，我们只需要用4个变量即可，因为我们每次用到的都是前面一个。
• 技巧：动态规划

java代码——基础思路

class Solution {
    public int minFlipsMonoIncr(String s) {
        // 前面全是0，后面全是1
        int len = s.length();
        int[] zDp = new int[len + 1];
        int[] oDp = new int[len + 1];
        for (int i = 0; i < len; i++) {
            if (s.charAt(i) == '1') {
                zDp[i + 1] = zDp[i] + 1;// 变成0
                oDp[i + 1] = Math.min(oDp[i], zDp[i]);// 保持1
            } else {
                zDp[i + 1] = zDp[i];// 保持0
                oDp[i + 1] = Math.min(oDp[i], zDp[i]) + 1;// 变成1
            }
        }
        return Math.min(oDp[len], zDp[len]);
    }
}

java代码——进阶思路

class Solution {
    public int minFlipsMonoIncr(String s) {
        // 前面全是0，后面全是1
        int len = s.length();
        int zerodp = 0, onedp = 0, newzerodp, newonedp;
        for (int i = 0; i < len; i++) {
            if (s.charAt(i) == '1') {
                newzerodp = zerodp + 1;
                newonedp = Math.min(zerodp, onedp);
            } else {
                newzerodp = zerodp;
                newonedp = Math.min(zerodp, onedp) + 1;
            }
            zerodp = newzerodp;
            onedp = newonedp;
        }
        return Math.min(zerodp, onedp);
    }
}

• 总结：题目有点难度，对我来说的话，因为动态规划的问题，我确实不太会，并且这个题还比较绕。也是花了好多时间才理清楚思路。