剑指 Offer II 092. 翻转字符 / 剑指 Offer II 093. 最长斐波那契数列

剑指 Offer II 092. 翻转字符【中等题】

思路：【动态规划】

二阶dp数组
dp[i][0]表示将第i位翻转为0后，数组保持递增的最小翻转次数
dp[i][1]表示将第i位翻转为1后，数组保持递增的最小翻转次数

初始状态：
dp[0][0] = s.charAt(0) == '0' ? 0 : 1
dp[0][1] = s.charAt(0) == '1' ? 0 : 1

转移方程：

dp[i][0] = dp[i-1][0]+s.charAt(i) == '0' ? 0:1
dp[i][1] = Math.min(dp[i-1][0],dp[i-1][1])+s.charAt(i) == '1' ? 0:1

代码：【dp数组】

class Solution {
    
    public int minFlipsMonoIncr(String s) {
    
        //动态规划解题
        int n = s.length();
        //dp二维数组
        // dp[i][0]表示将第i位翻转为0时，使字符串s单调递增的最小翻转次数，此时i-1处的字符必须为0
        // dp[i][1]表示将第i位翻转为1时，使字符串s单调递增的最小翻转次数，此时i-1处的字符可以为0也可以为1
        int[][] dp = new int[n][2];
        dp[0][0] = s.charAt(0) == '0' ? 0 : 1;//第0位字符为0,则dp[0][0]=0,否则为1
        dp[0][1] = s.charAt(0) == '1' ? 0 : 1;//第0位字符为1,则dp[0][1]=0,否则为1
        for (int i = 1; i < n; i++) {
    
            int k1 = 0,k2 = 0;
            if (s.charAt(i) == '0'){
    
                k2++;
            }else {
    
                k1++;
            }
            //将第i位翻转为0的最小翻转次数 为 dp[i-1][0] + (s[i] == ‘1’ ？ 1 ： 0)
            dp[i][0] = dp[i-1][0] + k1;
            //将第i位翻转为1的最小翻转次数 为 Math.min(dp[i-1][0],dp[i-1[1]) + (s[i] == '0' ? 1 : 0)
            dp[i][1] = Math.min(dp[i-1][0],dp[i-1][1]) + k2;
        }
        //最后返回将第n-1位翻转为0或者翻转为1的较小值
        return Math.min(dp[n-1][0],dp[n-1][1]);
    }
}

代码：【滚动数组】

class Solution {
    
    public int minFlipsMonoIncr(String s) {
    
        //动态规划解题
        int n = s.length();
        //滚动数组模拟dp数组
        // dp0表示将第i位翻转为0时，使字符串s单调递增的最小翻转次数，此时i-1处的字符必须为0
        // dp1表示将第i位翻转为1时，使字符串s单调递增的最小翻转次数，此时i-1处的字符可以为0也可以为1
        int dp0 = s.charAt(0) == '0' ? 0 : 1;//第0位字符为0,则dp[0][0]=0,否则为1
        int dp1 = s.charAt(0) == '1' ? 0 : 1;//第0位字符为1,则dp[0][1]=0,否则为1
        for (int i = 1; i < n; i++) {
    
            int k1 = 0,k2 = 0;
            if (s.charAt(i) == '0'){
    
                k2++;
            }else {
    
                k1++;
            }
            //将第i位翻转为0的最小翻转次数 为 dp[i-1][0] + (s[i] == ‘1’ ？ 1 ： 0)
            k1 += dp0;
            //将第i位翻转为1的最小翻转次数 为 Math.min(dp[i-1][0],dp[i-1[1]) + (s[i] == '0' ? 1 : 0)
            k2 += Math.min(dp0,dp1);
            
            dp0 = k1;
            dp1 = k2;
        }
        //最后返回将第n-1位翻转为0或者翻转为1的较小值
        return Math.min(dp0,dp1);
    }
}

---

剑指 Offer II 093. 最长斐波那契数列【中等题】

思路：【动态规划】【双指针】

参考题解
动态规划+双指针，就是快！

代码：

class Solution {
    
    public int lenLongestFibSubseq(int[] arr) {
    
        int n = arr.length,max = 0;
        //dp[i][j]为arr数组中以下标 i j 位置的数字为结尾的合法斐波那契数列，dp[i][j]的值表示所表示的斐波那契数列的长度
        int[][] dp = new int[n][n];
        //遍历数组，以遍历到的数字arr[k]为目标合法斐波那契数列子序列的结束位置
        for (int k = 2; k < n; k++) {
    
            //定义双指针 i 和 j 其中 i表示目标合法斐波那契数列子序列的起始位置，初值为 0，j表示目标合法斐波那契数列子序列结束位置的前一位，初值为 k-1
            int i = 0, j = k-1;
            //当 i < j 时，在[i,j]窗口内筛选是否存在 目标合法斐波那契数列子序列
            while (i < j){
    
                //当 arr[i] + arr[j] == arr[k]时，说明找到了一个以 j k 位置数字结束的合法斐波那契数列（这里简写为jk目标）
                if (arr[i] + arr[j] == arr[k]){
    
                    //如果 dp[i][j] == 0 表示以 i j 位置数字结束的所有子序列无法构成合法斐波那契数列，所以 jk目标的长度只能是 3
                    if (dp[i][j] == 0){
    
                        dp[j][k] = 3;
                    }else {
    
                        //否则 jk目标的长度等于 ij目标的长度+1 与 jk目标的长度 两者之间的最大值
                        dp[j][k] = Math.max(dp[i][j]+1,dp[j][k]);
                    }
                    //此时更新max为 max 和 jk目标长度 两者之间的最大值
                    max = Math.max(max,dp[j][k]);
                    //i指针右移 j指针左移 继续在窗口内寻找合法斐波那契数列子序列
                    i++;
                    j--;
                }else if (arr[i] + arr[j] < arr[k]){
    
                    //当 arr[i] + arr[j] < arr[k]时，根据arr递增的这一性质，为了使 arr[i] + arr[j] ==> arr[k],我们应该尝试右移i，然后重新判断
                    i++;
                }else {
    
                    //当 arr[i] + arr[j] > arr[k]时，根据arr递增的这一性质，为了使 arr[i] + arr[j] ==> arr[k],我们应该尝试左移j，然后重新判断
                    j--;
                }
            }
        }
        //程序执行过程中，max保持始终是 合法斐波那契数列长度的最大值，因此根据题意程序结束时返回max即可
        return max;
    }
}