8. 暴力递归
8.1 汉诺塔问题8.2 打印全部子序列8.3 打印字符串的全部排列8.4 打印字符串的不重复全部排列8.5 纸牌8.6 逆序栈8.7 字符串转化8.8 装袋问题 总结
8. 暴力递归暴力递归就是尝试
1，把问题转化为规模缩小了的同类问题的子问题
2, 有明确的不需要继续进行递归的条件（base case)
3，有当得到了子问题的结果之后的决策过程
4，不记录每一个子问题的解
一定要学会怎么去尝试，因为这是动态规划的基础，这一内容我们将在提升班讲述
8.1 汉诺塔问题0：45：0
三个杆，大的不能压小的，
package class08;
public class Code01_Hanoi {
public static void hanoi(int n) {
if (n > 0) {
func(n, n, "left", "mid", "right");
}
}
// 1~i 圆盘 目标是from -》 to ， other是另外一个
public static void func(int rest, int down, String from, String help, String to) {
if (rest == 1) {// base case
System.out.println("move " + down + " from " + from + " to " + to);
} else {
func(rest - 1, down - 1, from, to, help);
func(1, down, from, help, to);
func(rest - 1, down - 1, help, from, to);
}
}
public static void main(String[] args) {
int n = 3;
hanoi(n);
}
}
8.2 打印全部子序列
打印一个字符串的全部子序列，包括空字符串
package class08;
import java.util.ArrayList;
import java.util.List;
public class Code02_PrintAllSubsquences {
public static void printAllSubsquence(String str) {
char[] chs = str.toCharArray();
process(chs, 0);
}
// 当前来到i位置，要和不要，走两条路
// 之前的选择，所形成的结果 是chs
public static void process(char[] chs, int i) {
if (i == chs.length) {
System.out.println(String.valueOf(chs));
return;
}
process(chs, i + 1);
char tmp = chs[i];
chs[i] = 0; // char数组 放入零， asic吗没有输出值
process(chs, i + 1);
chs[i] = tmp;
}
public static void function(String str) {
char[] chs = str.toCharArray();
process(chs, 0, new ArrayList());
}
// 当前来到i位置，要和不要，走两条路
// res 之前的选择，所形成的列表
public static void process(char[] chs, int i, List res) {
if(i == chs.length) {
printList(res);
}
List resKeep = copyList(res);
resKeep.add(chs[i]);
process(chs, i+1, resKeep); // 要当前字符的路
List resNoInclude = copyList(res);
process(chs, i+1, resNoInclude);// 不要当前字符的路
}
public static void printList(List res) {
// ...;
}
public static List copyList(List list){
return null;
}
public static void main(String[] args) {
String test = "abc";
printAllSubsquence(test);
}
}
8.3 打印字符串的全部排列
leetcode46
打印一个字符串的全部排列
打印一个字符串的全部排列，要求不要出现重复的排列
回溯就是在递归的基础之上在每一个步骤上进行标记和取消标记的处理
package class08;
import java.util.ArrayList;
public class Code03_PrintAllPermutations {
public static ArrayList Permutation(String str) {
ArrayList res = new ArrayList<>();
if (str == null || str.length() == 0) {
return res;
}
char[] chs = str.toCharArray();
process(chs, 0, res);
res.sort(null);
return res;
}
// str[i...] 范围上， 所有的字符，都可以在i位置上 ，后续都去尝试
// str[0...i-1] 范围上，是之前做的选择
// 请把所有的字符串形成的全排列，加到res上去
public static void process(char[] chs, int i, ArrayList res) {
if (i == chs.length) {
res.add(String.valueOf(chs));
}
//boolean[] visit = new boolean[26];
for (int j = i; j < chs.length; j++) {
// if (!visit[chs[j] - 'a']) {
// visit[chs[j] - 'a'] = true;
swap(chs, i, j);
process(chs, i + 1, res);
swap(chs, i, j);
// }
}
}
public static void swap(char[] chs, int i, int j) {
char tmp = chs[i];
chs[i] = chs[j];
chs[j] = tmp;
}
}
8.4 打印字符串的不重复全部排列
分支限界。剪枝。
不重复
package class08;
import java.util.ArrayList;
public class Code03_PrintAllPermutations {
public static ArrayList Permutation(String str) {
ArrayList res = new ArrayList<>();
if (str == null || str.length() == 0) {
return res;
}
char[] chs = str.toCharArray();
process(chs, 0, res);
res.sort(null);
return res;
}
// str[i...] 范围上， 所有的字符，都可以在i位置上 ，后续都去尝试
// str[0...i-1] 范围上，是之前做的选择
// 请把所有的字符串形成的全排列，加到res上去
public static void process(char[] chs, int i, ArrayList res) {
if (i == chs.length) {
res.add(String.valueOf(chs));
}
boolean[] visit = new boolean[26]; // 试过还是没试过
for (int j = i; j < chs.length; j++) {
if (!visit[chs[j] - 'a']) {//没试过 就试
visit[chs[j] - 'a'] = true;
swap(chs, i, j);
process(chs, i + 1, res);
swap(chs, i, j);
// }
}
}
public static void swap(char[] chs, int i, int j) {
char tmp = chs[i];
chs[i] = chs[j];
chs[j] = tmp;
}
}
8.5 纸牌
后手函数
package class08;
public class Code08_CardsInLine {
public static int win1(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
return Math.max(f(arr, 0, arr.length - 1), s(arr, 0, arr.length - 1));
}
public static int f(int[] arr, int i, int j) {
if (i == j) {
return arr[i];
}
return Math.max(arr[i] + s(arr, i + 1, j), arr[j] + s(arr, i, j - 1));
}
public static int s(int[] arr, int i, int j) {
if (i == j) {
return 0;
}
return Math.min(f(arr, i + 1, j), f(arr, i, j - 1));
}
public static int win2(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int[][] f = new int[arr.length][arr.length];
int[][] s = new int[arr.length][arr.length];
for (int j = 0; j < arr.length; j++) {
f[j][j] = arr[j];
for (int i = j - 1; i >= 0; i--) {
f[i][j] = Math.max(arr[i] + s[i + 1][j], arr[j] + s[i][j - 1]);
s[i][j] = Math.min(f[i + 1][j], f[i][j - 1]);
}
}
return Math.max(f[0][arr.length - 1], s[0][arr.length - 1]);
}
public static void main(String[] args) {
int[] arr = { 1, 9, 1 };
System.out.println(win1(arr));
System.out.println(win2(arr));
}
}
8.6 逆序栈
给你一个栈，请你逆序这个栈，不能申请额外的数据结构，只能使用递归函数。如何实现？
package class08;
import java.util.Stack;
public class Code04_ReverseStackUsingRecursive {
public static void reverse(Stack stack) {
if (stack.isEmpty()) {
return;
}
int i = getAndRemoveLastElement(stack);
reverse(stack);
stack.push(i);
}
public static int getAndRemoveLastElement(Stack stack) {
int result = stack.pop();
if (stack.isEmpty()) {
return result;
} else {
int last = getAndRemoveLastElement(stack);
stack.push(result);
return last;
}
}
public static void main(String[] args) {
Stack test = new Stack();
test.push(1);
test.push(2);
test.push(3);
test.push(4);
test.push(5);
reverse(test);
while (!test.isEmpty()) {
System.out.println(test.pop());
}
}
}
8.7 字符串转化
规定1和A对应、2和B对应、3和C对应…
那么一个数字字符串比如“111"，就可以转化为“AAA”、"KA”和"AK”。
给定一个只有数字字符组成的字符串str，返回有多少种转化结果。
1：47：00
package class08;
public class Code06_ConvertToLetterString {
public static int number(String str) {
if (str == null || str.length() == 0) {
return 0;
}
return process(str.toCharArray(), 0);
}
// i之前的位置，如何转化已经做过决定了
// i.. 有多少种转化结果
public static int process(char[] chs, int i) {
if (i == chs.length) {
return 1;
}
if (chs[i] == '0') {
return 0;
}
if (chs[i] == '1') {
int res = process(chs, i + 1); // i自己作为单独的部分，后续有多少种方法
if (i + 1 < chs.length) {
res += process(chs, i + 2);// （i和i+1）作为单独的部分，后续有多少种方法
}
return res;
}
if (chs[i] == '2') {
int res = process(chs, i + 1);// i自己作为单独的部分，后续有多少种方法
// （i和i+1）作为单独的部分并且没有超过26，后续有多少种方法
if (i + 1 < chs.length && (chs[i + 1] >= '0' && chs[i + 1] <= '6')) {
res += process(chs, i + 2);
}
return res;
}
//chs[i] == '3'~'9'
return process(chs, i + 1);
}
public static void main(String[] args) {
System.out.println(number("11111"));
}
}
8.8 装袋问题
package class08;
public class Code07_Knapsack {
public static int maxValue1(int[] weights, int[] values, int bag) {
return process1(weights, values, 0, 0, bag);
}
// i... 的货物选择， 形成最大的价值返回
// 重量永远不会超过bag
// 之前做的决定，所达到的重量， alreadyweight
public static int process1(int[] weights, int[] values, int i, int alreadyweight, int bag) {
if (alreadyweight > bag) {
return 0;
}
if (i == weights.length) {
return 0;
}
return Math.max(
process1(weights, values, i + 1, alreadyweight, bag),
values[i] + process1(weights, values, i + 1, alreadyweight + weights[i], bag));
}
public static int maxValue2(int[] c, int[] p, int bag) {
int[][] dp = new int[c.length + 1][bag + 1];
for (int i = c.length - 1; i >= 0; i--) {
for (int j = bag; j >= 0; j--) {
dp[i][j] = dp[i + 1][j];
if (j + c[i] <= bag) {
dp[i][j] = Math.max(dp[i][j], p[i] + dp[i + 1][j + c[i]]);
}
}
}
return dp[0][0];
}
public static void main(String[] args) {
int[] weights = { 3, 2, 4, 7 };
int[] values = { 5, 6, 3, 19 };
int bag = 11;
System.out.println(maxValue1(weights, values, bag));
System.out.println(maxValue2(weights, values, bag));
}
}
总结
基础阶段结束，然后把前面的代码全部自己打一边，并在leetcode上跑通。并在有些经典代码在python上也实现下，准备下蓝桥杯。
