14、算法与数据结构 - 实战：递归
汉诺塔问题
/**
* 汉诺塔问题
* Created by huangjunyi on 2022/9/1.
*/
public class Recursive01 {
public static void move(int level, String from, String to, String other) {
if (level == 1) {
// 只剩下一层，直接挪过去
System.out.println(from + " -> " + to);
} else {
// 0~n-1 from => other
move(level - 1, from, other, to);
// n from => to
System.out.println(from + " -> " + to);
// 0~n-1 other => to
move(level - 1, other, to, from);
}
}
}
不使用额外空间使得栈中元素逆序
/**
* 不使用额外空间使得栈中元素逆序
* Created by huangjunyi on 2022/9/2.
*/
public class Recursive02 {
public static int getBottom(Stack<Integer> stack) {
int result = stack.pop();
if (stack.isEmpty()) {
return result;
} else {
int bottom = getBottom(stack);
stack.push(result);
return bottom;
}
}
public static void reverse(Stack<Integer> stack) {
if (stack.isEmpty()) return;
int bottom = getBottom(stack);
reverse(stack);
stack.push(bottom);
}
}
给定一个字符串，返回所有不重复的子序列
例如abc，则返回a, ab, abc, b, bc, c
/**
* 给定一个字符串，返回所有不重复的子序列
* Created by huangjunyi on 2022/9/2.
*/
public class Recursive03 {
public static List<String> getSubSeq(String str) {
char[] chars = str.toCharArray();
Set<String> set = new HashSet<>();
String path = "";
int index = 0;
process(chars, index, set, path);
List<String> list = new ArrayList<>();
// 收集到的所有答案，放到set中去重
list.addAll(set);
return list;
}
private static void process(char[] chars, int index, Set<String> set, String path) {
// base case：index越界，遍历完所有字符，收集一个答案
if (index == chars.length) {
set.add(path);
return;
}
// 每个位置 要 不要 两个递归
process(chars, index + 1, set, path);
process(chars, index + 1, set, path + chars[index]);
}
}
给定一个字符串，返回不重复的全排序
例如abc, 返回abc, acb, bac, cab, bca, cba
/**
* 给定一个字符串，返回不重复的全排序
* Created by huangjunyi on 2022/9/2.
*/
public class Recursive04 {
public static List<String> getAllSortedResult(String str) {
// set用于收集到的所有答案去重
Set<String> set = new HashSet<>();
int i = 0;
char[] chars = str.toCharArray();
process(chars, i, set);
List<String> list = new ArrayList<>();
list.addAll(set);
return list;
}
private static void process(char[] chars, int index, Set<String> set) {
// base case：index越界，收集一个答案
if (index == chars.length) {
set.add(String.valueOf(chars));
}
// 每个位置index，从index开始，与后面每个位置交换，跑一个递归
for (int i = index; i < chars.length; i++) {
swap(chars, index, i);
process(chars, index + 1, set);
// 恢复现场
swap(chars, index, i);
}
}
private static void swap(char[] chars, int i, int j) {
char temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
}
}
字符串的数据转化为字母的结果
- 给定一个只由数字组成的字符串，1对应A，2对应B…
- 将字符串的数据转化为字母，如11，可以转化为AA，也可以转化为K
- 问：有多少种转化结果
/**
* 给定一个只由数字组成的字符串，1对应A，2对应B...
* 将字符串的数据转化为字母，如11，可以转化为AA，也可以转化为K
* 问：有多少种转化结果
* Created by huangjunyi on 2022/9/2.
*/
public class Recursive05 {
public static int getThransferCount(String str) {
char[] chars = str.toCharArray();
return process(chars, 0);
}
private static int process(char[] chars, int i) {
if (i == chars.length) return 1;
int res = 0;
if (chars[i] == '0') return res;
res += process(chars, i + 1);
if (chars[i] == '1') {
if (i + 1 < chars.length) {
res += process(chars, i + 2);
}
}
if (chars[i] == '2') {
if (i + 1 < chars.length && chars[i + 1] >='0' && chars[i + 1] <= '6') {
res += process(chars, i + 2);
}
}
return res;
}
}
背包问题（递归求解，不使用动态规划）
- 给定一组物品，物品有重量和价值两个属性（int[] weights，int[] values两个数组表示）
- 给定一个背包，背包限制只能承载有限重量（int bag一个整形表示）
- 问背包承载的最大物品总价值是多少？
/**
* 背包问题
* Created by huangjunyi on 2022/9/2.
*/
public class Recursive06 {
public static int process(int[] weights, int[] values, int bag) {
return process(weights, values, 0, bag);
}
private static int process(int[] weights, int[] values, int index, int space) {
if (space < 0 || index == weights.length) return 0;
// 当前位置物品不要，之间下一轮递归
int p1 = process(weights, values, index + 1, space);
int p2 = Integer.MIN_VALUE;
if (space >= weights[index]) {
//如果背包还有空间放得下当前物品，参数装入当前物品，进行下一轮递归
p2 = values[index] + process(weights, values, index + 1, space - weights[index]);
}
//递归返回，总p1,p2中取最大值
return Math.max(p1, p2);
}
}
N皇后问题（位运算求解）
在一个N*N的棋盘上摆放N个皇后，规定每个皇后的位置不能同行，不能同列，也不能同对角线
/**
* N皇后问题（位运算版）
* Created by huangjunyi on 2022/9/3.
*/
public class Recursive08 {
public static int nQueue(int n) {
if (n > 32) return -1;
int limit = n == 32 ? -1 : 1 << n - 1;
int leftLimit = 0; // 左对角线限制
int rightLimit = 0; // 右对角线限制
int column = 0; // 已放皇后的列
return process(limit, column, leftLimit, rightLimit);
}
private static int process(int limit, int column, int leftLimit, int rightLimit) {
if (limit == column) return 1;
int res = 0;
int pos = limit & (~(column|leftLimit|rightLimit)); //可以放皇后的所有位置，&运算是排除范围外的1的干扰
while (pos != 0) {
int currPos = pos & (~pos + 1); //每次提前出当前可放皇后位置的最右侧的1
res += process(limit, column|currPos, (leftLimit|currPos) << 1, (rightLimit|currPos) >> 1);
pos ^= currPos; //该位置已经尝试过放皇后，去除该位置
}
return res;
}
}
纸牌游戏
- 给定一个整形数组，代表一串纸牌
- 有A、B两个玩家，从中抽取纸牌，但是每次只能拿最左或者最右侧的纸盘
- 假设两个玩家双方都绝顶聪明
- 求最后获胜方的结果值
/**
* 给定一个整形数组，代表一串纸牌
* 有A、B两个玩家，从中抽取纸牌，但是每次只能拿最左或者最右
* 假设两个玩家双方都绝顶聪明
* 求最后获胜方的结果值
* Created by huangjunyi on 2022/9/3.
*/
public class Recursive07 {
/**
* 先手拿牌
* @param values
* @param left
* @param right
* @return
*/
public static int first(int[] values, int left, int right) {
if (left == right) return values[left];
return Math.max(values[left] + second(values, left + 1, right), values[right] + second(values, left, right - 1));
}
/**
* 后手拿牌
* @param values
* @param left
* @param right
* @return
*/
public static int second(int[] values, int left, int right) {
if (left == right) return 0;
return Math.min(first(values, left + 1, right), first(values, left, right - 1));
}
public static int getWinValue(int[] values) {
return Math.max(first(values, 0, values.length - 1), second(values, 0, values.length - 1));
}
}