[算法入门笔记] 8. 暴力递归

提示：本篇主要讲述的是基于二叉树的暴力递归模型

文章目录

• 1. 汉诺塔问题
• 2. 递归函数逆序栈
• 3. 数字字符串转字母组合的方法数
• 4. 背包问题
• 5. 纸牌博弈问题
• 6. N皇后
• • 6.1 暴力破解
  • 6.2 位运算加速（仅限32皇后内）

1. 汉诺塔问题

public void hanoi(int n) {if(n > 0) {func(n, "左", "右", "中");}
}public void process(int i, String start, String end, String other) {if (i == 1) { // 终止条件// 仅剩一枚盘子 直接放过去System.out.println("Move 1 from " + start + "to" + end);} else {//i - 1 from -> otherfunc(i - 1, start, other, end);//i from ->  toSystem.out.println("Move " + i + "from " + start + "to" + end);//i - 1 other -> tofunc(i - 1, other, end, start);}
}

2. 递归函数逆序栈

[问题] 使用递归函数逆序栈，不允许申请额外空间

递归函数1：将栈stack的栈底元素返回并移除

public int getAndRemoveLastElement(Stack<Integer> stack) {int result = stack.pop();if (stack.isEmpty()) { // 递归结束条件return result;} else {int last = getAndRemoveLastElement(stack);stack.push(result);return last;}
}

递归函数2：逆序一个栈

public void reverse(Stack<Integer> stack) {if (stack.isEmpty()) {return;} else {// 获取栈底元素int i =getAndRemoveLastElement(stack);reverse(stack);stack.push(i);}
}

分析

只能利用栈操作和递归逆序栈，栈一次仅能对一个元素操作，所以只能从弹出栈底出发，然后压栈操作

3. 数字字符串转字母组合的方法数

[问题] 规定1和A对应、2和B对应、3和C对应… 那么一个数字字符串比如"111"，就可以转化为AAA、KA和AK。 给定一个只有数字字符组成的字符串str，返回有多少种转化结果。

算法思路

定义递归函数process(i)，其含义是str[0...i-1]是已经做好的决定，str[i..N]是没有转换完毕的，最后返回合法答案。

• 情况1 p(n)表示当前来到尾部，答案已经转换完毕，只有一种结果
• 情况2 不满足情况1且str[i]='0'，说明是以’0’开头的违规情况，返回0种结果
• 情况3 当前i是以1开头，两种情况，其一是以str[i]构成个位数的答案，其二是以str[i]和str[i+1]构成两位数的答案
• 情况4 当前i是以2开头，两种情况，其一是以str[i]构成个位数的答案，其二是在以str[i]和str[i+1]构成两位数不超过26情况下构成另一种答案
• 情况5 剩余的情况是以3-9开头只有一种答案
• 综上相加即为返回结果

// 暴力尝试 来到i位置返回的种数
//  i str[0..i-1]表示已经转换完毕，str[i..]表示还没转换的情况下
public int process(char[] str, int i) {if (i == str.length) { // 递归终止条件// 表示str[0..n-1]转换完毕，没有后续字符了，答案一种return 1;}if (str[i] == '0') {// 之前转换成，但遇到了0，进入无效状态return 0;}// 以'1'开头后续的答案if (str[i] == '1') {// i自己作为单独部分，后续的答案 1位情况下的答案int res = process(str, i + 1);// i和i+1作为单独部分，后续的的答案 两位的情况下的答案if (i + 1 < str.length) {res +=process(str, i + 2);}return res;}// 以'2'开头后续的答案if (str[i] == '2') {// i自己作为单独部分，后续的答案 1位情况下的答案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;}// 当前i指向的字符是3-9，只有一种情况return process(str, i + 1);
}

4. 背包问题

[问题] 给定两个长度都为N的数组weights和values，weights[i]和values[i]分别代表i号物品的重量和价值。给定一个正数bag，表示一个载重bag的袋子，你装的物品不能超过这个重量。返回你能装下最多的价值是多少？

提示：典型的从左向右尝试模型

/*** 暴力递归* @param weights 货物重量* @param values 货物价值* @param i i位置* @param alreadyweight 之前选择货物所达到的重量* @param bag 载重* @return  [i..]的货物自由选则，形成最大价值返回*/
public int process(int[] weights, int[] values, int i, int alreadyweight, int bag) {if (alreadyweight > bag) { // 违规条件return 0;}if (i == weights.length) { // 终止条件// 到了末尾没有东西可拿了，价值为0return 0;}// 两条路径 // 路径1 选择当前i位置的货物// 路径2 不选择当前i位置的货物// 返回两种路径中最大的货物价值return Math.max(// 路径1 选择当前货物value[i] + process(weights, values, i + 1, alreadyweight + weight[i], bag),// 路径2 不选择当前货物process(weights, values, i + 1, alreadyweight, bag));
}

5. 纸牌博弈问题

[问题] 给定一个整型数组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。

先手玩家

/**
* 先手拿牌的宝贝返回的分数，先手必然拿的最好的牌
* @param arr 牌组
* @param i 左边界
* @param j 右边界
* @return 返回分数
*/
public int first(int[] arr, int i, int j) {if (i == j) { // 递归终止条件//当牌只有一张，先手必然拿到return arr[i];}/*** 1.先手拿走了arr[i]，剩下的必然后手* 2.先手拿走了arr[j]，剩下的必然后手* 3.返回较大的分数*/return Math.max(// 先手拿走了arr[i]，剩下的必然后手arr[i] + second(arr, i + 1, j),// 先手拿走了arr[j]，剩下的必然后手arr[j] + second(arr, i, j - 1));
}

后手玩家

/*** 后手拿牌的宝贝返回的分数，后手必然拿的差的牌* @param arr 牌* @param i 左边界* @param j 右边界* @return*/
public int second(int[] arr, int i, int j) {if (i == j) { // 递归终止条件// 只剩一张牌时，作为后手必然拿不到return 0;}/*** 1.对手先拿牌，对手拿走了arr[i]，后手从arr[i+1..j]拿* 2.对手先拿牌，对手拿走了arr[j]，后手从arr[i..j-1]拿* 3.返回最差的分数*/return Math.min(// 对手先拿牌，对手拿走了arr[i]，后手从arr[i+1..j]拿的分数first(arr, i + 1, j),// 对手先拿牌，对手拿走了arr[j]，后手从arr[i..j-1]拿的分数first(arr, i, j - 1));
}

赢家

public int win(int[] arr) {if(arr == null || arr.length == 0) {return 0;}return Math.max(first(arr, 0, arr.length - 1), second(arr, 0, arr.length - 1));
}

6. N皇后

[问题] N皇后问题是指在N×N的棋盘上要摆N个皇后，要求任何两个皇后不同行、不同列，也不在同一条斜线上。给定一个整数n，返回n皇后的摆法有多少种。
n=1，返回1。
n=2或3，2皇后和3皇后问题无论怎么摆都不行，返回0。
n=8，返回92。

6.1 暴力破解

算法思想

从第i行开始摆放皇后，在$(i,j)$位置放置了一个皇后，接下来

• 整个第i行位置不能放皇后
• 整个第j列位置不能放皇后
• 如果位置$(a,b)$满足$|a-i|==|b-j|$，说明两点共斜线，不能放置皇后

判断摆放位置是否合法

// 目前在i行放皇后，record[0:i-1] 需要注意，record[i...] 不需要注意
// 返回i行皇后，放在j列，是否合法
public 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;
}

暴力递归

// record[i]表示第i行皇后所在的列数
public int process(int i, int[] record, int n) {if (i == n) { // 终止条件// 之前做的选择来到终止位置，有一种结果return 1;}int res = 0;// 在当前i行 0...n-1列尝试for (int j = 0; j < n; j++) {// 当前i行的皇后放在j列，会不会和之前的(0..i-1)行的皇后，共行共列或共斜线// 若是，认为无效；若不是，认为有效if(isValid(record, i, j)) {record[i] = j;// 尝试下一行res += process1(i + 1, record, n);}}return res;
}

最终调用

public int NQueens(int n) {if (n < 1) {return 0;}// record[i]表示第i行的皇后放在第几列int[] record = new int[n];/*** 0 从第0行放皇后* record 存放列的信息* n 不能超过n行*/return process1(0, record, n);
}

6.2 位运算加速（仅限32皇后内）

[算法图示]

process

// colLim 列的限制，1的位置不能放皇后，0的位置可以
// leftDiaLim 左斜线的限制，1的位置不能放皇后，0的位置可以
// rightDiaLim 右斜线的限制，1的位置不能放皇后，0的位置可以
public int process(int limit, int colLim, int leftDiaLim,int rightDiaLim) {// n行的n皇后放完了if (colLim == limit) {// 列限制放完了，没地方放了return 1;}int pos = 0;int mostRightOne = 0;// colLim | leftDiaLim | rightDiaLim 总限制// pos代表目前能放皇后的位置pos = limit & (~(colLim | leftDiaLim | rightDiaLim));int res = 0;// pos上几个1循环几次while (pos != 0) {// mostRightOne代表在pos中，最右边的1在什么位置，// 然后从右到左依次筛选出pos中可选择的位置进行尝试mostRightOne = pos & (~pos + 1);pos = pos - mostRightOne;// 下一行怎么尝试res += process2(limit, colLim | mostRightOne,  // 列限制或当前的决定(leftDiaLim | mostRightOne) << 1, // 左限制或当前决定整体左移(rightDiaLim | mostRightOne) >>> 1);// 右限制或当前决定整体右移}return res;
}

最终调用

public int NQueens(int n) {// 违规条件if (n < 1 || n > 32) {return 0;}// 生成二进制数，譬如，9皇后 该二进制数表示低9位是1，高位全是0int limit = n == 32 ? -1 : (1 << n) - 1;return process2(limit, 0, 0, 0);
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！