左神一周刷爆LeetCode 8 暴力递归

柔情只为你懂 2024-03-27 14:08 10阅读 0赞

#### 左神一周刷爆LeetCode ####

[【一周刷爆LeetCode，算法大神左神（左程云）耗时100天打造算法与数据结构基础到高级全家桶教程，直击BTAJ等一线大厂必问算法面试题真题详解】][LeetCode_100_BTAJ]

![在这里插入图片描述][21d8730943004734a7556c22ae9ac043.png_pic_center]

#### 8 暴力递归 ####

##### 8.1 暴力递归就是尝试 #####

1.  把问题转化为规模缩小了的同类问题的子问题
2.  有明确的不需要继续进行递归的条件(base case)
3.  有当得到了子问题的结果之后的决策过程
4.  不记录每一个子问题的解

一定要学会怎么去尝试，因为这是动态规划的基础。

##### 8.2 汉诺塔问题 #####

打印n层汉诺塔从最左边移动到最右边的全部过程

Java代码实现：

package class08;
    
    public class Code01_Hanoi {
        
    
        public static void hanoi(int n) {
        
            if (n > 0) {
        
                func(n, "左", "右", "中");
            }
        }
    
        // 1~i 圆盘目标是from → to, other是另一个
        public static void func(int i, String start, String end, String other) {
        
    
            if (i == 1) {
        
                System.out.println("Move 1 from " + start + " to " + end);
            } else {
        
                func(i - 1, start, other, end);
                System.out.println("Move " + i + " from " + start + " to " + end);
                func(i - 1, other, end, start);
            }
        }
    
        public static void main(String[] args) {
        
            int n = 3;
            hanoi(n);
        }
    
    }

![在这里插入图片描述][071bad19c58d4364ae2b3a76f819b80f.png_pic_center]

##### 8.3 打印一个字符串的全部子序列，包括空字符串 #####

打印一个字符串的全部子序列，包括空字符串

Java代码实现

package class08;
    
    import java.util.ArrayList;
    import java.util.List;
    
    public class Code02_PrintAllSubsquences {
        
    
       public static void printAllSubsquence(String str) {
        
          char[] chs = str.toCharArray();
          process(chs, 0);
       }
    
       // 一种省空间的做法【复用 str空间】
       // 当前来到i 位置, 要和不要, 走两条路
       // 之前的选择, 所形成的结果是str【即边做决策的过程中，str 是变化的】
       public static void process(char[] str, int i) {
        
          // 来到终止位置,直接打印str
          if (i == str.length) {
        
             System.out.println(String.valueOf(str));
             return;
          }
    
          process(str, i + 1); // 要当前字符的路
          char tmp = str[i]; // 把当前位置记下
          str[i] = 0;
          process(str, i + 1); // 不要当前字符的路
          str[i] = tmp;
       }
       
       public static void function(String str) {
        
          char[] chs = str.toCharArray();
          process(chs, 0, new ArrayList<Character>());
       }
    
       // 当前来到i 位置, 要和不要, 走两条路
       // res之前的选择, 所形成的列表
       public static void process(char[] str, int i, List<Character> res) {
        
          // 来到终止位置, 打印之前的选择
          if(i == str.length) {
        
             printList(res);
          }
          List<Character> resKeep = copyList(res);
          resKeep.add(str[i]);
          process(str, i+1, resKeep); // 要当前字符的路
          List<Character> resNoInclude = copyList(res);
          process(str, i+1, resNoInclude); // 不要当前字符的路
       }
       
       public static void printList(List<Character> res) {
        
          // ...;
       }
       
       public static List<Character> copyList(List<Character> list){
        
          return null;
       }
       
    
       public static void main(String[] args) {
        
          String test = "abc";
          printAllSubsquence(test);
       }
    
    }

![在这里插入图片描述][1ecf90c1f34d44e98df4644e3873de9e.png_pic_center]

##### 8.4 打印一个字符串的全部排列 #####

打印一个字符串的全部排列，要求不要出现重复的排列

Java代码实现：

public static ArrayList<String> Permutation(String str) {
        
        ArrayList<String> res = new ArrayList<>();
        if (str == null || str.length() == 0) {
        
            return res;
        }
        char[] chs = str.toCharArray();
        process(chs, 0, res);
        return res;
    }
    
    // str[i..] 范围上, 所有的字符, 都可以在 i位置上, 后续都去尝试
    // str[0..i-1] 范围上, 是之前做的选择
    // 把所有的字符串形成的全排列, 加入到 res 中去
    // str 承载着我之前做的选择
    public static void process(char[] str, int i, ArrayList<String> res) {
        
        // i 来到结尾，将str 的样子加入res
        if (i == str.length) {
        
            res.add(String.valueOf(str));
        }
        boolean[] visit = new boolean[26]; // 不重复进行全排列
        for (int j = i; j < str.length; j++) {
         // i往后所有的字符都可以来到i位置
            if (!visit[str[j] - 'a']) {
         // 当前字符没试过我才试【分支限界】【提前杀死不行的路】
                visit[str[j] - 'a'] = true;
                swap(str, i, j);
                process(str, i + 1, res);
                swap(str, i, j);
            }
        }
    }
    
    public static void swap(char[] chs, int i, int j) {
        
        char tmp = chs[i];
        chs[i] = chs[j];
        chs[j] = tmp;
    }

##### 8.5 逆序栈 #####

给你一个栈，请你逆序这个栈，不能申请额外的数据结构，只能使用递归函数。 如何实现?

Java代码实现：

public static void reverse(Stack<Integer> stack) {
        
       if (stack.isEmpty()) {
        
          return;
       }
       int i = getAndRemoveLastElement(stack);
       reverse(stack);
       stack.push(i);
    }
    
    public static int getAndRemoveLastElement(Stack<Integer> stack) {
        
       int result = stack.pop();
       if (stack.isEmpty()) {
        
          return result;
       } else {
        
          int last = getAndRemoveLastElement(stack);
          stack.push(result);
          return last;
       }
    }

【太强了orz】

##### 8.6 字符串与数字字符 #####

规定1和A对应、2和B对应、3和C对应… 那么一个数字字符串比如"111"，就可以转化为"AAA"、“KA"和"AK”。

给定一个只有数字字符组成的字符串str，返回有多少种转化结果。

Java代码实现：

package class08;
    
    public class Code06_ConvertToLetterString {
        
    
       public static int number(String str) {
        
          if (str == null || str.length() == 0) {
        
             return 0;
          }
          return process(str.toCharArray(), 0);
       }
    
       // i 之前的位置, 如何转换已经做过决定了
       // i... 有多少种转换的结果
       public static int process(char[] str, int i) {
        
          if (i == str.length) {
         // i来到末尾, 返回一种即之前做的决定
             return 1;
          }
          if (str[i] == '0') {
         // 之前做的决定让当前状态没法儿转了, 这种情况无后续0种
             return 0;
          }
          if (str[i] == '1') {
        
             int res = process(str, i + 1); // i自己作为单独的部分, 后续有多少种方法
             if (i + 1 < str.length) {
        
                res += process(str, i + 2); // (i 和 i + 1)作为单独的部分, 后续有多少种方法
             }
             return res;
          }
          if (str[i] == '2') {
        
             int res = process(str, i + 1); // i自己作为单独的部分, 后续有多少种方法
    
             // (i 和 i + 1)作为单独的部分并且没有超过26, 后续有多少种方法
             if (i + 1 < str.length && (str[i + 1] >= '0' && str[i + 1] <= '6')) {
        
                res += process(str, i + 2);
             }
             return res;
          }
          // str[i] == '3' ~ '9'
          return process(str, i + 1);
       }
    
       public static void main(String[] args) {
        
          System.out.println(number("111"));
       }
    
    }

![在这里插入图片描述][47d35752fb9449558cf3d1f35293a4eb.png_pic_center]

##### 8.7 最大价值 #####

给定两个长度都为N的数组weights和values，weights\[i\]和values\[i\]分别代表 i号物品的重量和价值。

给定一个正数bag，表示一个载重bag的袋子，你装的物品不能超过这个重量。返回你能装下最多的价值是多少？

Java代码实现：

public static int maxValue1(int[] weights, int[] values, int bag) {
        
       return process1(weights, values, 0, 0, bag);
    }
    
    // i... 的货物自由选择, 形成的最大价值返回
    // 重量永远不要超过bag
    // 之前做的决定, 所达到的重量alreadyweight
    public static int process1(int[] weights, int[] values, int i, int alreadyweight, int bag) {
        
       if (alreadyweight > bag) {
         // 超重了,方案不该有
          return 0;
       }
       if (i == weights.length) {
         // 没货了
          return 0;
       }
       return Math.max( 
    
             process1(weights, values, i + 1, alreadyweight, bag),
    
             values[i] + process1(weights, values, i + 1, alreadyweight + weights[i], bag));
    }

这是暴力递归。

DP改写：【成败完全决定于我们暴力递归的试法】

public static int maxValue2(int[] c, int[] p, int bag) {
        
       int[][] dp = new int[c.length + 1][bag + 1];
       for (int i = c.length - 1; i >= 0; i--) {
        
          for (int j = bag; j >= 0; j--) {
        
             dp[i][j] = dp[i + 1][j];
             if (j + c[i] <= bag) {
        
                dp[i][j] = Math.max(dp[i][j], p[i] + dp[i + 1][j + c[i]]);
             }
          }
       }
       return dp[0][0];
    }

##### 8.8 获胜者分数 #####

给定一个整型数组arr，代表数值不同的纸牌排成一条线。玩家A和玩家B依次拿走每张纸牌，规定玩家A先拿，玩家B后拿，但是每个玩家每次只能拿走最左或最右的纸牌，玩家A 和玩家B都绝顶聪明。请返回最后获胜者的分数。

【举例】 arr=\[1,2,100,4\]。 开始时，玩家A只能拿走1或4。如果开始时玩家A拿走1，则排列变为\[2,100,4\]，接下来 玩家 B可以拿走2或4，然后继续轮到玩家A… 如果开始时玩家A拿走4，则排列变为\[1,2,100\]，接下来玩家B可以拿走1或100，然后继 续轮到玩家A… 玩家A作为绝顶聪明的人不会先拿4，因为拿4之后，玩家B将拿走100。所以玩家A会先拿1， 让排列变为\[2,100,4\]，接下来玩家B不管怎么选，100都会被玩家 A拿走。玩家A会获胜， 分数为101。所以返回101。 arr=\[1,100,2\]。

开始时，玩家A不管拿1还是2，玩家B作为绝顶聪明的人，都会把100拿走。玩家B会获胜， 分数为100。所以返回100。

Java代码实现：

public static int win1(int[] arr) {
        
       if (arr == null || arr.length == 0) {
        
          return 0;
       }
       return Math.max(f(arr, 0, arr.length - 1), s(arr, 0, arr.length - 1));
    }
    
    public static int f(int[] arr, int i, int j) {
        
       if (i == j) {
        
          return arr[i];
       }
       return Math.max(arr[i] + s(arr, i + 1, j), arr[j] + s(arr, i, j - 1));
    }
    
    public static int s(int[] arr, int i, int j) {
        
       if (i == j) {
        
          return 0;
       }
       return Math.min(f(arr, i + 1, j), f(arr, i, j - 1));
    }

改成DP

public static int win2(int[] arr) {
        
       if (arr == null || arr.length == 0) {
        
          return 0;
       }
       int[][] f = new int[arr.length][arr.length];
       int[][] s = new int[arr.length][arr.length];
       for (int j = 0; j < arr.length; j++) {
        
          f[j][j] = arr[j];
          for (int i = j - 1; i >= 0; i--) {
        
             f[i][j] = Math.max(arr[i] + s[i + 1][j], arr[j] + s[i][j - 1]);
             s[i][j] = Math.min(f[i + 1][j], f[i][j - 1]);
          }
       }
       return Math.max(f[0][arr.length - 1], s[0][arr.length - 1]);
    }

##### 8.9 N皇后问题【经典版】 #####

N皇后问题是指在N\*N的棋盘上要摆N个皇后，要求任何两个皇后不同行、不同列， 也不在同一条斜线上。

给定一个整数n，返回n皇后的摆法有多少种。

n=1，返回1。

n=2或3，2皇后和3皇后问题无论怎么摆都不行，返回0。

n=8，返回92。

【暴力试】

Java 代码实现：【时间复杂度  N N N^N NN】

public static int num1(int n) {
        
       if (n < 1) {
        
          return 0;
       }
       int[] record = new int[n]; // record[i] 表示 第i行的皇后放在了第几列
       return process1(0, record, n);
    }
    
    // 潜台词: record[0..i-1] 的皇后, 任何两个皇后一定不共行、不共列、不共斜线【这是我们在设置record的时候就一定要做到的事情】
    // 尝试过程
    // i: 现在来到了第几行，即第i行 
    // record[0...i-1]: 之前摆的皇后都在这里面【位置】
    // n: 整体一共多少行
    // 返回值: 摆完所有皇后, 合理的摆法有多少种
    public static int process1(int i, int[] record, int n) {
        
       if (i == n) {
         // 终止行, 咱们没有索引为n 的行，最大为n-1【来到终止行，就是一种了】
          return 1;
       }
       int res = 0;
       for (int j = 0; j < n; j++) {
         // 当前行是i 行，尝试i行对应的所有列即j
          
          // 当前i行的皇后, 放在j列，会不会和之前(0..i-1)的皇后, 共行共列共斜线
          // 如果是 → 有效，如果不是 → 无效
          if (isValid(record, i, j)) {
        
             record[i] = j;
             res += process1(i + 1, record, n);
          }
       }
       return res;
    }
    
    // 检查当前 i行皇后放在了j列，是否有效【因为我们是从行起手的，所以i和j 一定不共行，这就是天然的】
    public static boolean isValid(int[] record, int i, int j) {
        
       for (int k = 0; k < i; k++) {
         // 之前的某个k 行的皇后
          if (j == record[k] || Math.abs(record[k] - j) == Math.abs(i - k)) {
        
             return false;
          }
       }
       return true;
    }
    
    // 不要超过32皇后问题【常数优化: 用位运算进行加速】
    public static int num2(int n) {
        
       if (n < 1 || n > 32) {
        
          return 0;
       }
       int upperLim = n == 32 ? -1 : (1 << n) - 1;
       return process2(upperLim, 0, 0, 0);
    }
    
    // colLim: 列的限制, 1的位置不能放皇后, 0的位置可以
    // leftDiaLim: 左斜线的限制, 1的位置不能放皇后, 0的位置可以
    // rightDiaLim: 右斜线的限制, 1的位置不能放皇后, 0的位置可以
    public static int process2(int upperLim, int colLim, int leftDiaLim,
          int rightDiaLim) {
        
       if (colLim == upperLim) {
         // base case
          return 1;
       }
       int pos = 0;
       int mostRightOne = 0;
       
       // 所有候选皇后的位置, 都在pos 上
       pos = upperLim & (~(colLim | leftDiaLim | rightDiaLim));
       int res = 0;
       while (pos != 0) {
        
          mostRightOne = pos & (~pos + 1);
          pos = pos - mostRightOne;
          res += process2(upperLim, colLim | mostRightOne,
                (leftDiaLim | mostRightOne) << 1,
                (rightDiaLim | mostRightOne) >>> 1);
       }
       return res;
    }

优化和不优化运行对比：

14 皇后问题：

![在这里插入图片描述][aa661a7d28d044afbaba6ac6fccdfbf2.png_pic_center]

15皇后问题：

![在这里插入图片描述][23baca8ddb30433292c3cc4596adaa94.png_pic_center]

一个1s 多，一个22s

[LeetCode_100_BTAJ]: https://www.bilibili.com/video/BV13g41157hK
[21d8730943004734a7556c22ae9ac043.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/01c984dc647e4fea87d0f1844daccc25.png
[071bad19c58d4364ae2b3a76f819b80f.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/819e091ffa61418abbc76d21bb4782dd.png
[1ecf90c1f34d44e98df4644e3873de9e.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/ef578fe71e354fba8367b170e1492b41.png
[47d35752fb9449558cf3d1f35293a4eb.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/9b19dcdedc3f4adfbf9aba4427a1088e.png
[aa661a7d28d044afbaba6ac6fccdfbf2.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/8cca4bc3d9b74ab1ae251b53dfc640da.png
[23baca8ddb30433292c3cc4596adaa94.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/f10f8b5eb3ea4955afc7341c80545ba0.png