暴力递归

暴力递归就是尝试

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

    汉诺塔问题

  • 打印n层汉诺塔从最左边移动到最右边的全部过程(大的塔牌不能在小塔牌上)

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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);
}
}

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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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); // 要当前字符
}

全排列

题解

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
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

    题解

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    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”
    1
    2
    3
    4
    5
    6
    从左到右试:[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,否则该情况不存在

    题解

    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
    // 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);
    }

    矩阵最小路径和

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

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

    题解

    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
    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);
    }