• 力扣——剑指 Offer II 092. 翻转字符


    题目

    在这里插入图片描述
    在这里插入图片描述

    解题思路

    一个很暴力的想法,在满足单调递增的前提下,使每一位分别取 1 或 0,去看看哪个结果小。

    递归函数定义int dp(StringBuilder sb, int ind, int pre) sb是字符串,ind 是字符串当前位,pre 是字符串前一位(0或1)

    dp函数表示:从字符串当前位ind开始到字符串结尾,这样一个子字符串,变为单调递增所需要翻转的最小次数。

    因此题目所求就是 dp(sb, 0, 0)。第0位的前一位为0。

    具体递归入口有四种情况,根据前一位是0或1 和 当前位是0或1来讨论,即

    当前位为0:
        前一位为0:
    
        前一位为1:
    
    当前位为1:
        前一位为0:
    
        前一位为1:
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    一开始递归函数定义不明确,导致无法形成重叠子问题,也就无法用备忘录来优化。
    在考虑备忘录优化的时候,需要明确备忘录的每一维分别代表什么。参考了这位大佬的题解Java 递归+二维DP+空间优化

    代码

    class Solution {
        int[][] memo;  // 备忘录
        public int minFlipsMonoIncr(String s) {
            int n = s.length();
            memo = new int[n + 1][2];
            for(int[] arr : memo){
                Arrays.fill(arr, -1);
            }
            return dp(s.toCharArray(), 0, 0);
        }
    
        int dp(char[] s, int ind, int pre){  // sb是字符串,ind 是字符串当前位,pre 是前一位
            if(ind == s.length){  // 到字符串结尾了,需要改变的字符为0,返回值为0
                return 0;
            }
            if(memo[ind][pre] != -1){
                return memo[ind][pre];
            }
    
            int res = 0;
    
            if(s[ind] == '0'){ // 当前位为0
                if(pre == 0){ // 前一位为 0
                    int a = dp(s, ind + 1, s[ind] - '0'); // 保持0不变
                    s[ind] = '1';
                    int b = dp(s, ind + 1, s[ind] - '0');  // 把当前0变为1,翻转次数加一
                    s[ind] = '0';
                    res += Math.min(a, b);  // 取两者中最小的情况
                }else if(pre == 1){ // 前一位为 1
                    s[ind] = '1';
                    res += dp(s, ind + 1, s[ind] - '0') + 1;  // 前一位为1,当前位为0,必须变成1
                    s[ind] = '0';
                }
            }else if(s[ind] == '1'){  // 当前位为1
                if(pre == 0){ // 前一位为 0
                    int a = dp(s, ind + 1, s[ind] - '0'); // 保持1不变
                    s[ind] = '0';
                    int b = dp(s, ind + 1, s[ind] - '0') + 1; // 把当前1变为0,翻转次数加一
                    s[ind] = '1';
                    res += Math.min(a, b); // 取两者中最小的情况
                }else if(pre == 1){
                    res += dp(s, ind + 1, s[ind] - '0'); // 前一位为1,当前位为1,当前1必须保持不变
                }
            }
    
            memo[ind][pre] = res;
            return res;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49

    优化后

    class Solution {
        int[][] memo;  // 备忘录
        public int minFlipsMonoIncr(String s) {
            int n = s.length();
            memo = new int[n + 1][2];
            for(int[] arr : memo){
                Arrays.fill(arr, -1);
            }
            return dp(s.toCharArray(), 0, 0);
        }
    
        int dp(char[] s, int ind, int pre){  // sb是字符串,ind 是字符串当前位,pre 是前一位
            if(ind == s.length){  // 到字符串结尾了,需要改变的字符为0,返回值为0
                return 0;
            }
            if(memo[ind][pre] != -1){
                return memo[ind][pre];
            }
    
            int res = 0;
    
            if(s[ind] == '0'){ // 当前位为0
                if(pre == 0){ // 前一位为 0
                    // 保持0不变;
                    // 把当前0变为1,翻转次数加一; 
                    // 取两者中较小的情况
                    res = Math.min(dp(s, ind + 1, 0), dp(s, ind + 1, 1) + 1);  
                }else if(pre == 1){ // 前一位为 1
                    res = dp(s, ind + 1, 1) + 1;  // 前一位为1,当前位为0,必须变成1
                }
            }else if(s[ind] == '1'){  // 当前位为1
                if(pre == 0){ // 前一位为 0
                    // 保持1不变; 
                    // 把当前1变为0,翻转次数加一; 
                    // 取两者中较小的情况
                    res = Math.min(dp(s, ind + 1, 1), dp(s, ind + 1, 0) + 1);  
                }else if(pre == 1){
                    res = dp(s, ind + 1, 1); // 前一位为1,当前位为1,当前1必须保持不变
                }
            }
    
            memo[ind][pre] = res;
            return res;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45

    一开始写的时候有个问题,就是在递归函数的参数中记录结果,递归到边界的时候得到结果,这样就是一个纯递归的思路。并没有转成子问题的形式,因此我后续进行备忘录优化始终无法成功。原因还是递归函数定义有问题。

    纯递归的代码

    class Solution {
        int[][][] memo;
        public int minFlipsMonoIncr(String s) {
            StringBuilder sb = new StringBuilder(s);
            int n = s.length();
            memo = new int[n + 1][2][2];
            for(int[][] arr : memo){
                for(int[] a : arr)
                    Arrays.fill(a, -1);
            }
            return dp(sb, 0, 0,0 ,sb.charAt(0) - '0');
        }
    
        int dp(StringBuilder sb, int ind, int cnt, int pre, int now){
            if(ind == sb.length()){
                return cnt;
            }
            if(memo[ind][pre][now] != -1){
                return memo[ind][pre][now];
            }
    
            int res = 0;
    
            if(sb.charAt(ind) == '0'){
                if(ind - 1 >= 0){
                    if(sb.charAt(ind - 1) == '0'){
                        int a = dp(sb, ind + 1, cnt, sb.charAt(ind - 1) - '0',0);
                        sb.setCharAt(ind, '1');
                        int b = dp(sb, ind + 1, cnt + 1, sb.charAt(ind - 1) - '0',1);
                        sb.setCharAt(ind, '0');
                        res += Math.min(a, b);
                    }else{
                        sb.setCharAt(ind, '1');
                        res += dp(sb, ind + 1, cnt + 1, sb.charAt(ind - 1) - '0',1);
                        sb.setCharAt(ind, '0');
                    }
                }else{
                    int a = dp(sb, ind + 1, cnt, 0,0);
                    sb.setCharAt(ind, '1');
                    int b = dp(sb, ind + 1, cnt + 1, 0,1);
                    sb.setCharAt(ind, '0');
                    res += Math.min(a, b);
                }
    
            }else{
                if(ind - 1 >= 0){
                    if(sb.charAt(ind - 1) == '0'){
                        int a = dp(sb, ind + 1, cnt, sb.charAt(ind - 1) - '0',1);
                        sb.setCharAt(ind, '0');
                        int b = dp(sb, ind + 1, cnt + 1, sb.charAt(ind - 1) - '0',0);
                        sb.setCharAt(ind, '1');
                        res += Math.min(a, b);
                    }else{
                        res += dp(sb, ind + 1, cnt, sb.charAt(ind - 1) - '0',1);
                    }
                }else{
                    int a = dp(sb, ind + 1, cnt, 0,1);
                    sb.setCharAt(ind, '0');
                    int b = dp(sb, ind + 1, cnt + 1, 0,0);
                    sb.setCharAt(ind, '1');
                    res += Math.min(a, b);
                }
            }
    
            memo[ind][pre][now] = res;
            return res;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68

    其中cnt就是最后的结果,这样可以通过数据量小的问题,但数据量大的问题必定会超时,而且无法利用记忆化搜索优化。

    总结

    不管是不是动态规划问题,首先写出递归的暴力解。如果超时,考虑有没有重叠子问题,此时就要注意递归函数的定义,递归函数的返回值应该是子问题的解。可能一开始结果保存在函数参数中是比较好想的。如果一开始写的递归函数是结果在函数参数里的形式,要考虑将结果定义在返回值中,此时需要明确递归函数的定义。

  • 相关阅读:
    华为笔记本电脑原装win10/win11系统恢复安装教程方法
    分类预测 | MATLAB实现SSA-CNN-BiLSTM麻雀算法优化卷积双向长短期记忆神经网络数据分类预测
    基于Python旅游景区景点售票系统设计与实现 开题报告
    使用Springboot开发前后端分离校园智能出行拼车系统
    企业聊天应用程序使用 Kubernetes
    只要5秒就能“克隆”本人语音!美玉学姐不再查寝,而是吃起了桃桃丨开源
    shell-运算符
    基于OpenCV批量分片高像素影像
    ChatGPT扇动翅膀后带来的蝴蝶效应
    前端面试手册
  • 原文地址:https://blog.csdn.net/m0_46283220/article/details/127611922