暴力递归
- 概述
- 题目一：汉诺塔问题
- 题目二：字符串的全部子序列问题
- 题目三：字符串的全排列问题（分支限界）
- 题目四：拿纸牌比最大问题
- 题目五：递归逆序栈
- 题目六：数字与字符串的转化问题
- 题目七：重量和价值问题
- 题目八：N皇后问题
概述
- 暴力递归就是尝试（局部尝试）
- 把问题转化为规模缩小了的同类问题的子问题
- 明确递归结束的条件（base case）
- 得到子问题的结果后有决策过程
- 不记录每一个子问题的解，尝试最重要
题目一：汉诺塔问题
- 思路：
（1）将 1 ~ n - 1 层移动到中间
（2）将 n 层移动到最右边
（3）将 1 ~ n - 1 层移动到最右边
public static void hanoi(int n){ if (n > 0){ move(n, "left", "mid", "right"); } } public static void move(int n, String from, String to, String temp){ //移动from：出发地；to：目的地；temp：辅助位置 if (n == 1){ //递归结束条件 System.out.println("Move 1 form " + from + " to " + to); } else { //问题规模的缩小 //移动 n - 1 由from到temp move(n - 1, from, temp, to); //移动 n 由from到to System.out.println("Move " + n + " from " + from + " to " + to); //移动n - 1 由temp到to move(n - 1, temp, to, from); } }
- 结果演示：
当 n = 3
题目二：字符串的全部子序列问题
- 思路：
尝试从0 到 n位置
（1）将字符串转化为字符数组，每个字符位置分为要和不要
（2）问题从0 到 n的位置，每次增加一个位置
（3）当长度等于 n 结束递归
注意点：一个递归结束后若对字符数组进行了改变，再下一个递归开始前要恢复字符数组
public static void printAllSubsquence(String str){ char[] chs = str.toCharArray(); progress(chs, 0); } public static void progress(char[] chs, int index){ //index，在字符数组中目前到达的位置 if (index == chs.length){ //走完整个字符数组 System.out.println(String.valueOf(chs)); return; } //直接后移保留index位置，规模的缩小 progress(chs, index + 1); char temp = chs[index]; //ASCLL中0表示空字符 chs[index] = 0; //将index出使用空字符代替，规模的缩小 progress(chs, index + 1); //恢复index位置 chs[index] = temp; }
- 结果演示
str = “ljk”
题目三：字符串的全排列问题（分支限界）
- 思路：
若字符串的长度为n
尝试从0到n位置
不考虑重复排列时：使用交换的方法
（1）第一个位置可以有N个位置与其交换
（2）第二个位置可以有N - 1个位置与其交换
……
（3）第N - 1个位置有2个位置可以与其交换
（4）第N个位置只有1个位置与其交换（递归结束的条件，交换到第N个位置）
注意点：一个递归结束后若对字符数组进行了改变，再下一个递归开始前要恢复字符数组
//全排列 public static void permutation(String str){ char[] chs = str.toCharArray(); progress(chs, 0); } public static void progress(char[] chs, int index){ //index，在字符数组中目前到达的位置 if (index == chs.length){ //走完整个字符数组 System.out.println(String.valueOf(chs)); return; } for (int i = index; i < chs.length; i++){ //index位置与其后面的位置进行交换 swap(chs, index, i); //规模的缩小 progress(chs, index + 1); //一次递归结束恢复原字符数组 swap(chs, index, i); } } public static void swap(char[] chs, int i, int j){ char temp = chs[i]; chs[i] = chs[j]; chs[j] = temp; }
- 结果演示
str = “abb”
- 思路：
若字符串的长度为n，字符均为小写字母
考虑重复排列时：出现相同的字母时不进行位置交换
public static void permutation(String str){ char[] chs = str.toCharArray(); progress(chs, 0); } public static void progress(char[] chs, int index){ //index，在字符数组中目前到达的位置 if (index == chs.length){ //走完整个字符数组 System.out.println(String.valueOf(chs)); return; } //记录26个小写字母是否有相同的 boolean[] visit = new boolean[26]; //默认为false for (int i = index; i < chs.length; i++) { if (!visit[chs[i] - 'a']) { //i位置的元素没有重复，可以与index位置交换 //分支限界的思想，提前结束不可能的分支 visit[chs[i] - 'a'] = true; //index位置与其后面的位置进行交换 swap(chs, index, i); //规模的缩小 progress(chs, index + 1); //一次递归结束恢复原字符数组 swap(chs, index, i); } } } public static void swap(char[] chs, int i, int j){ char temp = chs[i]; chs[i] = chs[j]; chs[j] = temp; }
- 结果演示：
str = “abb"
题目四：拿纸牌比最大问题
- 思路：
（1）分为两种拿牌方式，先手和后手，若范围为left ~ right
（2）先手分为左右，若拿left，值就是就是left位置的值 + 后手的值(left + 1 ~ right后手)；若拿right，值就是right位置的值 + 后手的值(left ~ right - 1后手)，返回二者值中较大的
（3）后手分为对手拿左还是右，若对手拿left，值就是先手的值(left + 1 ~ right先手)；若拿right，值就是先手的值(left ~ right - 1先手)，因为对手一定拿最优解，那么后手一定是二者值中较小的情况
（4）若 left == right 先手就是 left位置的值，后手就是0
public static int win(int[] arr){ if (arr == null || arr.length == 0){ return 0; } int valueA = first(arr, 0, arr.length - 1); //A的先手情况 int valueB = second(arr, 0, arr.length - 1); //B的后手情况 return Math.max(valueA, valueB); } public static int first(int[] arr, int left, int right){ //先手获得的最好分数 if (left == right){ //递归结束条件 return arr[left]; } int l = arr[left] + second(arr, left + 1, right); //拿左边 int r = arr[right] + second(arr, left, right - 1); //拿右边 return Math.max(l, r); } public static int second(int[] arr, int left, int right){ //先手获得的最好分数 if (left == right){ //递归结束条件 return 0; } int l = first(arr, left + 1, right); //对手拿走了左边 int r = first(arr, left, right - 1); //对手拿走了右边 //因为对手一定会挑选最优情况，所以留给后手一定是俩者中较差的选择 return Math.min(l, r); }
- 结果演示：
arr = [1, 100, 2]
题目五：递归逆序栈
- 思维：
（1）利用系统栈保存数据的性能解决问题
（2）首先要实现得到栈底元素的函数，使用递归一直调用该函数是元素出栈，若栈为空返回栈底元素， 否则返回递归的临时变量
（3）逆序函数的实现，一次逆序就是得到栈底元素，递归调用，直至栈为空，重新压入系统栈的保存数据
public static void reverse(Stack<Integer> stack){ //逆序栈 if (stack.isEmpty()){ //栈空返回 return; } //得到栈底元素 int bottom = getBottom(stack); //递归调用 reverse(stack); //栈空后重新压入，利用系统栈的保存数据 stack.push(bottom); } public static int getBottom(Stack<Integer> stack){ //得到栈底元素 int result = stack.pop(); if (stack.isEmpty()){ //到达栈底返回 return result; } //递归调用 int temp = getBottom(stack); //将非栈底元素重新压入栈 stack.push(result); //temp在系统栈中保存递归数据 return temp; }
- 结果演示：
题目六：数字与字符串的转化问题
- 思路：
从左往右的尝试
在数组中index为当前遍历到的位置，尝试index位置的所有可能出现的情况后，index继续移动，直至数组结束即可 - 情况分析：
（1）若index位置出现0，说明前面转化出错，返回0
（2）若index位置为 1 或 2，可以考虑与 index + 1位置结合转化，也可以单独转化，产生两种递归的方式：直接到下一个位置，或者跳过下一个位置
（3）若index位置为3 ~ 9，就直接单独转化，没有产生多余的情况，直接递归到下一个位置
（4）若index等于数组长度，说明此次转化结束返回 1
public static int number(String str){ if (str == null || str.length() == 0){ return 0; } return process(str.toCharArray(), 0); } public static int process(char[] chs, int index){ //遍历数组 if (index == chs.length){ //index到最后一个说明此次递归得到了一种情况 return 1; } if (chs[index] == '0'){ //index位置出现0，说明此次递归出错 return 0; } if (chs[index] == '1'){ //index位置出现1 //单独转化index位置 int result = process(chs, index + 1); if (index + 1 < chs.length){ //结合index + 1位置转化 result += process(chs, index + 2); } return result; } if (chs[index] == '2') { //index位置出现2 //单独转化index位置 int result = process(chs, index + 1); if (index + 1 < chs.length && (chs[index + 1] <= '6')){ //结合index位置转化 //该转化时，数字小于等于26 result += process(chs, index + 2); } return result; } //index位置为 3 ~ 9 return process(chs, index + 1); }
- 结果演示：
str = “121451202”
题目七：重量和价值问题
- 思路：
尝试位置0 ~ i，分为要和不要
（1）记录当前重量，若超过bag，则无法获得
（2）若要，当前重量增加，价值增加，遍历下一个；若不要直接遍历到下一个
（3）若已经将全部都遍历完则返回0
public static int maxValue(int[] weights, int[] values, int bag){ if (weights.length == 0){ return 0; } return process(weights, values, bag, 0, 0); } public static int process(int[] weights, int[] values, int bag, int index, int alreadyWeight){ //index：目前遍历到的位置 //alreadyWeight：目前的重量 if (index == values.length){ //已经全部遍历完 return 0; } int getValue; if (alreadyWeight + weights[index] <= bag){ //当前仍然可以增加index的重量 //要index位置的物品，alreadyWeight增加，返回value的增加 getValue = values[index] + process(weights, values, bag, index + 1, alreadyWeight + weights[index]); }else { //无法增加，与noValue相同 getValue = process(weights, values, bag, index + 1, alreadyWeight); } //不要index位置的物品，value, alreadyWeight均不变 int noValue = process(weights, values, bag, index + 1, alreadyWeight); //决策出两者的较大值，返回 return Math.max(getValue, noValue); }
- 结果演示：
weights = [10, 3, 7, 8, 9]
values = [4, 2, 3, 9, 5]
bag = 20
题目八：N皇后问题
- 思路：
（1）尝试在每一行的不同列位置放一个皇后
（2）要求：以后放的都不能与前面的同列或者同斜线
public static int num(int n){ if (n < 0){ return 0; } //record[i]表示第 i - 1行的皇后放在第几列 int[] record = new int[n]; return process(0, record, n); } public static int process(int index, int[] record, int n){ //index目前遍历到的行 //n为棋盘大小 if (index == n){ //遍历正常完成，之前的摆放正确 return 1; } int result = 0; for (int row = 0; row < n; row++){ //当前index行，皇后放到row列 if (isValid(record, index, row)){ //若位置有效 record[index] = row; result += process(index + 1, record, n); } } return result; } public static boolean isValid(int[] record, int index, int row){ //判断加入的皇后是否合法 for (int i = 0; i < index; i++){ //遍历之前行加入的皇后 if (record[i] == row || Math.abs(record[i] - row) == Math.abs(i - index)){ //判断是否同列，或者同斜线 //同列的判断：两点的斜率是否为1(45度)，或者-1(135度) //就是行差的绝对值与列差的绝对值是否相同 return false; } } return true; }
- 结果演示：
n = 8
