暴力递归算法总结

前言

该文章旨在复习左程云算法与数据结构基础班暴力递归算法，对应视频:

https://www.bilibili.com/video/BV13g41157hK?p=11
https://www.bilibili.com/video/BV13g41157hK?p=12

暴力递归

暴力递归，顾名思义就是把所有的情况全部穷举一遍，然后看正确的是那些，并且保存下来，对于这种题没有固定的模板，对于不同的问题，有着不同的业务要求，有着不同的暴力策略，我们直接来一道题进入这个算法的奇妙之中。

字符串的子序列

无重字符

想要生成生成一个字符串的所有子序列，应该对其每个位置的字符进行选择，可选是否选择这个字符，或者不选择这个字符，你可以把选择这个过程放在一颗二叉树上，选择的节点就是新生成的字符串，而路径就是是否选择该字符，而遍历的过程其实就是生成一个这样的二叉树，我们获取答案，只需在每个节点走到树底的位置保存即可。

一起来看下代码实现把：

public static void printAllSubsquences(String str) {
    // 先把字符串转为字符数组
    char[] chs = str.toCharArray();
    // 调用递归函数，用一个字符列表保存，并初始化了列表的大小，节省内存。
    process(chs, 0, new ArrayList<>(chs.length));
}

// 递归函数主体，传入参数字符数组，递归的数组的位置，和用来保存答案的列表。
public static void process(char[] chs, int i, List<Character> res) {
    // base case：当前字符数组遍历完了，来到了下一层，无法继续遍历，那么就打印生成好了的答案
    if (i == chs.length) {
        System.out.println(res);
        // 结束当前的递归函数
        return;
    }
    // 以传入的字符列表作为基准，重新生成一个字符列表
    List<Character> resKeep = new ArrayList<>(res);
    // 并选择当前的字符
    res.add(chs[i]);
    // 进入下一次递归（左子树）
    process(chs, i + 1, resKeep);
    // 同理重新创建一个字符列表，但是这次不做选择，直接进行下一次递归调用
    List<Character> resNoInclude = new ArrayList<>(res);
    // 左子树遍历完后回来进行遍历右子树
    process(chs, i + 1, resNoInclude);
}

需要注意的是，这个代码仅适用于不存在重复字符的字符串。

有重字符

寻找有重字符的字符串的子序列相当于对这个字符串转成字符数组再进行全排列，这里就需要用到回溯算法，在前文回溯算法解决排列/组合/子集问题已经提到过了，不清楚可以看一下。

public static void printAllSubsquences(String str) {
    // 字符串转字符数组
    char[] chs = str.toCharArray();
    // 记录所有答案的字符串列表
    List<String> res = new ArrayList<>();
    // 调用递归函数，参数：数组列表、下标、记录答案的列表
    backtrack(chs, 0, res);
    System.out.println(res.stream().collect(Collectors.joining(",")));
}

// 回溯算法
public static void backtrack(char[] chs, int start, List<String> res) {
    // base case 递归位置到达数组最后一个索引+1的位置，已经遍历完数组了，答案就已经生成好了，直接保存即可
    if (start == chs.length) {
        res.add(new String(chs));
        return;
    }
    // 使用一个数组记录该元素是否被添加过，防止出现重复
    boolean[] visited = new boolean[26];
    for (int j = start; j < chs.length; j++) {
        // 如果该元素没有被添加到visited里，进入分支结构
        if (!visited[chs[j] - 'a']) {
            // 设置该元素已经被访问过了
            visited[chs[j] - 'a'] = true;
            // 交换当前未遍历过的元素和当前正在遍历的元素
            // 这里其实是做一次选择，选择了chs[j]这个元素
            // 在循环中，从start到chs.length-1的位置未添加过的都会做出选择并进入下一层递归
            swap(chs, start, j);
            // 回溯进入下一层
            backtrack(chs, start + 1, res);
            // 撤销选择，递归回来后，恢复原来的位置，保证循环到其他元素时是独立的
            swap(chs, start, j);
        }
    }
}

// 交换字符数组内元素
public static void swap(char[] chs, int i, int j) {
    char tmp = chs[i];
    chs[i] = chs[j];
    chs[j] = tmp;
}

拿牌游戏

这个题目就比较有意思，给定一个牌库数组arr，其中两个玩家轮流从卡牌的一端拿牌，目的是使自己拿到的牌的点数总和最大化，最后一定会有一个人会赢，得出最后赢得人的点数，而且这两人都非常聪明，每一步都是使自己最大化的一步。

对于这个问题，我们设计了两个函数一个为f，一个为s。

它们的定义是这样的（我们这个视角的人物一定是最后获得最大点数的人，设为玩家A，另一个为玩家B）:

f函数定义：对于这个玩家A先手时，玩家A在L到R区间获取到的最大分数。
s函数定义：对于这个玩家A后手时，玩家A在L到R区间获取的最小分数。因为玩家B很聪明会使玩家A最小化分数，自身最大化分数。

有了清晰的定义，我们就可以知道如何实现这个游戏了：
我们假设玩家A就是先手，那么我们就开始调用f(arr,0,arr.length-1)来开始这个游戏，设置arr为[1,100,3,4]。

• 最开始玩家A先手，他有两个选择，一个是拿左边的1，一个是拿右边的4，但是拿了1的话，聪明的玩家B接下来一定会拿100，那么玩家A一定会输，那么玩家A会拿4。
• 然后玩家B先手（也就是玩家A后手了），玩家B不论拿哪个都会使接下来的玩家A拿到100，那么只能拿一个相对于1大一点的3了，使自身最大化。
• 然后玩家A又先手，拿了100
• 最后玩家B先手，拿下1，
• 结算玩家A共拿了104，玩家B拿了4。

知道了这个游戏流程，我们一起来看一下代码：

public class 拿牌游戏 {
    public static void main(String[] args) {
        int[] arr = {1, 100, 3, 4};
        System.out.println(f(arr, 0, arr.length - 1));
    }

    // 玩家A先手，玩家B后手
    public static int f(int[] arr, int L, int R) {
        // base case 只剩一张牌了，直接拿上，arr[L]和arr[R]等效的，随便一个都行
        if (L == R) return arr[L];
        // 假设拿上左边的，那么总点数就是先手拿上左边的+后手在L+1到R这个区间的点数。
        int l = arr[L] + s(arr, L + 1, R);
        // 假设拿上右边的，那么总点数就是先手拿上右边的+后手在L到R-1这个区间的点数。
        int r = arr[R] + s(arr, L, R - 1);
        // 最后对比两个假设的值，获取最大的那个，使自己的点数最大化
        return Math.max(l, r);
    }

    // 玩家B先手，玩家A后手
    public static int s(int[] arr, int L, int R) {
        // base case 还是只剩一张牌，虽然是B先手，但是我们是在玩家A视角的，也就是不拿，返回点数0
        if (L == R) return 0;
        // 假设玩家B拿了左边的，那么我们下一次就是先手，拿L+1到R上最大的点数。
        int l = f(arr, L + 1, R);
        // 假设玩家B拿了右边的，那么我们下一次就是先手，拿L到R-1上最大的点数。
        int r = f(arr, L, R - 1);
        // 虽然我们是在玩家A视角的，但是现在是玩家B先手，所以玩家B聪明的使自己最大化点数，最小化玩家A的点数
        // 所以选择两种假设的最小值
        return Math.min(l, r);
    }
}

两个函数互相递归调用，最后得到合理博弈得到的最大的点数。，这道题我反复琢磨了好几遍，是这篇文章中最难的了应该（，值得反复推敲啊，确实很有意思。

汉诺塔

经典汉诺塔问题，要求把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
这里有一个在线的小游戏，可以直观感受一下：

汉诺塔可视化小游戏

算法实现过程是这样的：

• 首先定义三个柱子，分别为左、中、右三个柱子，现在圆盘都在左上，我们要把其上面都移动到右上面
• 将左上1-n-1的圆盘，移动到中柱子上
• 再将左上最大的圆盘移动到右
• 然后递归的调用，将中上1-n-2的圆盘移动到左柱子上……
• 直到最后就剩下一个圆盘，直接将其放到右上面即可，至此就结束了

public class 汉诺塔 {
    // 递归函数
    public static void move(int n, char from, char inter, char to) {
        if (n == 1) {
            // 只有一个圆盘时，直接移动到目标柱子
            System.out.println("Disk 1 from " + from + " to " + to);
        } else {
            // 将最上面的n-1个圆盘从起始柱子移动到中间柱子
            move(n - 1, from, to, inter);
            // 将最大的圆盘从起始柱子移动到目标柱子
            System.out.println("Disk " + n + " from " + from + " to " + to);
            // 将n-1个圆盘从中间柱子移动到目标柱子
            move(n - 1, inter, from, to);
        }
    }

    public static void main(String[] args) {
        int n = 3; // 圆盘数目
        move(n, 'A', 'B', 'C'); // A为起始柱子，B为中间柱子，C为目标柱子
    }
}

逆序栈

给定一个栈，把其内的所有元素反转过来。听起来这个问题很简单，我们再借助一个队列就可以完成，但是我们要求不使用额外的数据结构，哎呀，这样可就不简单了呢，我们怎么办呢？可以利用递归函数调用的系统栈，这样不算额外的数据结构。
思路：我们递归的依次弹出栈底元素，直到栈为空时达到base case，往回归，然后再归的时候依次把弹出的栈底元素压入栈顶即可实现反转栈。

说的很明白了已经，我们要先实现一个函数，作用是是取得栈底的元素，这样才能在归的时候拿到元素并重新压回栈顶

public static int f(Stack<Integer> stack) {
    // 拿到栈顶元素
    int result = stack.pop();
    // base case
    if (stack.isEmpty()) {
        // 如果栈空了，说明已经到栈底了，直接返回栈底元素
        return result;
    } else {
        // 根据函数定义拿到栈底元素
        int last = f(stack);
        // 递归返回的是栈底元素，为不改变原栈结构，所以在归的时候要把最先弹出的栈顶元素再放回去
        stack.push(result);
        // 然后返回栈底元素，切记不能再压入栈后再调用函数，例如return f(stack);这样
        // 那样就变成了前序位置，无法再调用后归回来，必须再调用函数后再压入栈顶
        return last;
    }
}

反转栈代码实现：

public static void r(Stack<Integer> stack){
    // base case 一直向下遍历栈，边遍历边取栈底元素，直到为空时
    if(stack.isEmpty()) return;
    // 根据定义拿到栈底元素
    int i = f(stack);
    // 递归调用栈
    r(stack);
    // 后序位置，归的时候将开始拿到的栈底元素压入栈，最后实现反转栈
    stack.push(i);
}

0/1背包问题

给的一些物品的重量与价值，和一个有限的背包，要求用背包拿这些物品中的一些物品使得价值最大化

public class 零一背包问题 {
    public static void main(String[] args) {
        int[] weights = {3, 2, 4, 7, 3, 1, 7};
        int[] values = {5, 6, 3, 19, 12, 4, 2};
        int bag = 15;
        System.out.println(maxValue(weights, values, bag, 0, 0));
    }

    // 返回值：最大价值
    public static int maxValue(int[] weights, int[] values, int bag, int i, int alreadyWeight) {
        // 如果已经超过背包容量，回滚上一次的总价值，即当前的总价值减去上一轮物品的价值就是上一轮的总价值
        // 因为上一轮的总价值是不包含当前物品的，所以要减去上一轮物品的价值
        if (alreadyWeight > bag) {
            return alreadyWeight - weights[i - 1];
        }
        // 如果已经遍历完所有物品，返回0
        if (i == weights.length) {
            return 0;
        }
        // 不要当前物品
        int p1 = maxValue(weights, values, bag, i + 1, alreadyWeight);
        // 要当前物品
        int p2 = values[i] + maxValue(weights, values, bag, i + 1, alreadyWeight + weights[i]);
        // 返回两种情况的最大值
        return Math.max(p1, p2);
    }
}

数字转化字符

将数字映射为字符，1-25分别对应a-z，返回这串数字转化成字符的种类有几种。
例如：数字11,可以被转化为aa和k。
注意：0不参与转化字符，如出现了这个数字，那么答案一定为0。

public class 数字转化字符 {
    public static void main(String[] args) {
        System.out.println(f("11".toCharArray(), 0)); // 输出结果是2
    }

    // 递归函数，用于计算解码方法的数目
    public static int f(char[] chs, int i) {
        // 如果索引i达到字符串的长度，意味着找到了一种解码方法，返回1计数
        if (i == chs.length) return 1;
        // 如果当前的字符是'0'，则当前分支不能构成有效的解码，返回0
        if (chs[i] == '0') return 0;
        // 如果当前的字符是'1'，可以直接解码当前字符，也可以将它与下一个字符一起解码
        if (chs[i] == '1') {
            int res = f(chs, i + 1); // 解码当前字符，递归计算后续字符
            if (i + 1 < chs.length) {
                // 如果还有下一个字符，尝试将当前字符和下一个字符一起解码
                res += f(chs, i + 2);
            }
            return res;
        }
        // 如果当前的字符是'2'，可以直接解码当前字符，但只有当下一个字符在0到6之间才能与当前字符一起解码
        if (chs[i] == '2') {
            int res = f(chs, i + 1); // 解码当前字符，递归计算后续字符
            if (i + 1 < chs.length && chs[i + 1] >= '0' && chs[i + 1] <= '6') {
                // 如果下一个字符存在且在'0'到'6'范围内，尝试将这两个字符一起解码
                res += f(chs, i + 2);
            }
            return res;
        }
        // 如果当前字符是'3'到'9'之间的任意字符，只能解码当前字符
        return f(chs, i + 1);
    }
}

结尾

至此，课上所有题目已经复习完毕，暴力递归，主要是考虑好函数的定义，才能在调用递归的时候易如反掌。