暴力递归

暴力递归就是尝试

把问题转化为规模缩小了的同类问题的子问题
有明确的不需要继续进行递归的条件（base case）
有当得到了子问题的结果之后的决策过程
不记录每一个子问题的解
汉诺塔问题
打印n层汉诺塔从最左边移动到最右边的全部过程(大的塔牌不能在小塔牌上)

题解

private static void hanoi(int n){
    if(n > 0){
        func(n,"左","右","中");
    }
}
//1~i 圆盘目标是from->to other是另一个
private static void func(int i, String start, String end, String other){
    //base
    if(i == 1){
        System.out.println("move 1 from " + start+ " to " + end);
    }else {
        // 将大规模问题化位小问题
        // 假设现在n层塔牌只有两层 1 和 i-1 层
        // 先把最上面的一大堆n-1左位置移到中位置
        func(i-1, start,other,end);// 左  中  右
        // 将剩下的最大塔牌从左位置移到右位置
        System.out.println("move " + i + " from " + start+ " to " + end);
        // 将一大堆n-1的塔牌从中位置移到右位置
        func(i-1,other,end,start);
    }
}

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

private static void printAllSub(String str){
       if(str == null){
           return;
       }
       char[] chars = str.toCharArray();
       if(chars.length > 0){
           String pre = new String("");   // pre：表示从0到i-1位置上形成的结果
           printAllSub(0, pre, chars);
       }else{
           System.out.println("");          // 输入空字符串也会打印空
       }
   }
   private static void printAllSub(int i, String pre, char[] chars){
       // 已经到数组最后一个字符了，所有的选择都做完了，该返回了
       if(i == chars.length){
           System.out.println(pre);
           return;
       }
       // 如果没有到最后一个字符，那么当前字符两种选择：选择要或者选择不要
       printAllSub(i + 1, pre, chars);                              // 不要当前字符
       printAllSub(i + 1, pre + String.valueOf(chars[i]), chars);   // 要当前字符
   }

全排列

题解

private static void printAllSort(String str) {

        if (str == null) {
            return;
        }
        char[] chars = str.toCharArray();
        if (chars.length > 0) {
            func(0, chars);
        }
    }

    private static void func(int i, char[] chars) {
        if (i == chars.length) {
            System.out.println(String.valueOf(chars));
        }
        for (int j = i; j < chars.length; j++) {
            swap(i,j,chars);  // 第i个位置有i~n-1这些选择
            func(i+1,chars);  // 搞第i+1的位置
            swap(i,j,chars);
        }
    }
    private static void swap(int i, int j, char[] chars){
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
    }

逆序栈问题

给你一个栈，请你逆序这个栈，不能申请额外的空间，只能使用递归函数，如何实现

1
2
3

1     递归取栈底元素               入栈             3
2 --> i = 3 --> i =2 -- > i = 1 -->   -->  2  --> 2
3                                   1      1      1

题解

private static void reverse(Stack<Integer> stack) {
    if (stack.isEmpty()) {
        return;
    }

    int i = f(stack);  // 接到栈底元素
    reverse(stack);    // 反转剩余元素 
    stack.push(i);     // 将栈底元素先入栈形成逆序 
}

//移除栈底元素并返回
private static int f(Stack<Integer> stack) {
    int result = stack.pop();
    if (stack.isEmpty()) {
        return result;
    } else {
        int last = f(stack);
        stack.push(result);
        return last;
    }
}

字母和数字对应问题

规定1和A对应，2和B对应，3和C对应…

那么一个数字字符串比如“111”，就可以转化为“AAA”，“KA”，和“AK”

从左到右试：[0…i-1]确定，[i…]可以变
(1)arr[i] == 0 --> return 0 无法组合
(2)arr[i] >= 3 --> i自己转，return i+1的结果
(3)arr[i] == 1 --> i自己转，return i+1的结果;i和i+1一块转，return i+2
(4)arr[i] == 2 --> i自己转，return i+1的结果;在i和i+1组成的数字不超过26的情况下，
                   i和i+1一块转，return i+2，否则该情况不存在

题解

// i 之前的位置，如何转化已做过决定了
// i... 有多少种转化结果
private static int process(char[] str,int i){
    if(i == str.length){
        return 1;
    }
    if(str[i] == '0'){
        return 0;
    }
    if(str[i] == '1'){
        //i作为单独的部分，后续有多少种方法
        int res = process(str,i+1);
        //i和i+1 一起作为一部分，后续有多少种方法
        if(i + 1 < str.length){
            res += process(str,i+2);
        }
        return res;
    }
    if(str[i] == '2'){
        //i作为单独的部分，后续有多少种方法
        int res = process(str,i + 1);
        //i和i+1 一起作为一部分，并且没有超过26，后续有多少种方法
        if(i + 1 < str.length && str[i + 1] >= '0' && str[i + 1] <= '6'){
            res += process(str,i + 2);
        }
        return res;
    }
    //当前字符是3~9
    return process(str,i + 1);
}

矩阵最小路径和

给你一个二维数组，二维数组中的每个数都是正数，要求从左上角走到右下角，
每一步只能向右或者向下。沿途经过的数字要累加起来。返回最小的路径和。

2-->5   3   5
    |
    V
7   1   3   4
    |
    V
4   2-->1-->6

题解

public static int minPath2(int[][] matrix){

        if(matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0){
            return 0;
        }
        // 从左上角走到右下角
        return walk(matrix, 0, 0);
    }
    private static int walk(int[][] matrix, int i, int j){

        if(i == matrix.length - 1 && j == matrix[0].length - 1){
            // [i,j]位置已经在右下角了
            return matrix[matrix.length - 1][matrix[0].length - 1];
        }
        if(i == matrix.length - 1){
            // [i,j]在矩阵的最后一行，所以只能往右走了
            return matrix[i][j] + walk(matrix, i, j + 1);
        }
        if(j == matrix[0].length - 1){
            // [i,j]在矩阵的最后一列，所以只能往下走了
            return matrix[i][j] + walk(matrix, i + 1, j);
        }

        int right = walk(matrix, i, j + 1);
        int down = walk(matrix, i + 1, j);
        return matrix[i][j] + Math.min(right,down);
    }

暴力递归

每日一句诗词

暴力递归

汉诺塔问题

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

全排列

逆序栈问题

字母和数字对应问题

矩阵最小路径和