- 暴力递归就是尝试
- 题目
- 汉诺塔问题,n层圆盘从左移到右打印移动过程(递归+非递归实现)
- 给你一个栈请你逆序这个栈不能申请额外数据结构,只能用递归函数。
- 打印一个字符串的全部子序列 & 打印一个字符串的全部子序列,要求不要出现重复字面值的子序列
- 打印一个字符串的全部排列 & 打印一个字符串的全部排列,要求不要出现重复的排列
- 从左往右的尝试模型
- 数字字符
- 背包问题
- 范围上尝试的模型
- 纸牌问题
- N皇后问题及位运算优化
- 把问题转化为规模缩小了的同类问题的子问题
- 有明确的不需要继续进行递归的条件(base case)
- 有当得到了子问题的结果之后的决策过程
- 不记录每一个子问题的解
package class17; import java.util.Stack; public class Code02_Hanoi { public static void hanoi1(int n) { leftToRight(n); } // 请把1~N层圆盘 从左 -> 右 public static void leftToRight(int n) { if (n == 1) { // base case System.out.println("Move 1 from left to right"); return; } leftToMid(n - 1); System.out.println("Move " + n + " from left to right"); midToRight(n - 1); } // 请把1~N层圆盘 从左 -> 中 public static void leftToMid(int n) { if (n == 1) { System.out.println("Move 1 from left to mid"); return; } leftToRight(n - 1); System.out.println("Move " + n + " from left to mid"); rightToMid(n - 1); } public static void rightToMid(int n) { if (n == 1) { System.out.println("Move 1 from right to mid"); return; } rightToLeft(n - 1); System.out.println("Move " + n + " from right to mid"); leftToMid(n - 1); } public static void midToRight(int n) { if (n == 1) { System.out.println("Move 1 from mid to right"); return; } midToLeft(n - 1); System.out.println("Move " + n + " from mid to right"); leftToRight(n - 1); } public static void midToLeft(int n) { if (n == 1) { System.out.println("Move 1 from mid to left"); return; } midToRight(n - 1); System.out.println("Move " + n + " from mid to left"); rightToLeft(n - 1); } public static void rightToLeft(int n) { if (n == 1) { System.out.println("Move 1 from right to left"); return; } rightToMid(n - 1); System.out.println("Move " + n + " from right to left"); midToLeft(n - 1); } public static void hanoi2(int n) { if (n > 0) { func(n, "left", "right", "mid"); } } public static void func(int N, String from, String to, String other) { if (N == 1) { // base System.out.println("Move 1 from " + from + " to " + to); } else { func(N - 1, from, other, to); System.out.println("Move " + N + " from " + from + " to " + to); func(N - 1, other, to, from); } } public static class Record { public boolean finish1; public int base; public String from; public String to; public String other; public Record(boolean f1, int b, String f, String t, String o) { finish1 = false; base = b; from = f; to = t; other = o; } } // 非递归版本 public static void hanoi3(int N) { if (N < 1) { return; } Stack给你一个栈请你逆序这个栈不能申请额外数据结构,只能用递归函数。stack = new Stack<>(); stack.add(new Record(false, N, "left", "right", "mid")); while (!stack.isEmpty()) { Record cur = stack.pop(); if (cur.base == 1) { System.out.println("Move 1 from " + cur.from + " to " + cur.to); if (!stack.isEmpty()) { stack.peek().finish1 = true; } } else { if (!cur.finish1) { stack.push(cur); stack.push(new Record(false, cur.base - 1, cur.from, cur.other, cur.to)); } else { System.out.println("Move " + cur.base + " from " + cur.from + " to " + cur.to); stack.push(new Record(false, cur.base - 1, cur.other, cur.to, cur.from)); } } } } public static void main(String[] args) { int n = 3; hanoi1(n); System.out.println("============"); hanoi2(n); // System.out.println("============"); // hanoi3(n); } }
package class17; import java.util.Stack; public class Code05_ReverseStackUsingRecursive { public static void reverse(Stack打印一个字符串的全部子序列 & 打印一个字符串的全部子序列,要求不要出现重复字面值的子序列stack) { if (stack.isEmpty()) { return; } int i = f(stack); reverse(stack); stack.push(i); } // 栈底元素移除掉 // 上面的元素盖下来 // 返回移除掉的栈底元素 public static int f(Stack stack) { int result = stack.pop(); if (stack.isEmpty()) { return result; } else { int last = f(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()); } } }
package class17; import java.util.ArrayList; import java.util.HashSet; import java.util.List; public class Code03_PrintAllSubsquences { // s -> "abc" -> public static List打印一个字符串的全部排列 & 打印一个字符串的全部排列,要求不要出现重复的排列subs(String s) { char[] str = s.toCharArray(); String path = ""; List ans = new ArrayList<>(); process1(str, 0, ans, path); return ans; } // str 固定参数 // 来到了str[index]字符,index是位置 // str[0..index-1]已经走过了!之前的决定,都在path上 // 之前的决定已经不能改变了,就是path // str[index....]还能决定,之前已经确定,而后面还能自由选择的话, // 把所有生成的子序列,放入到ans里去 public static void process1(char[] str, int index, List ans, String path) { if (index == str.length) { ans.add(path); return; } // 没有要index位置的字符 process1(str, index + 1, ans, path); // 要了index位置的字符 process1(str, index + 1, ans, path + String.valueOf(str[index])); } public static List subsNoRepeat(String s) { char[] str = s.toCharArray(); String path = ""; HashSet set = new HashSet<>(); process2(str, 0, set, path); List ans = new ArrayList<>(); for (String cur : set) { ans.add(cur); } return ans; } public static void process2(char[] str, int index, HashSet set, String path) { if (index == str.length) { set.add(path); return; } String no = path; process2(str, index + 1, set, no); String yes = path + String.valueOf(str[index]); process2(str, index + 1, set, yes); } public static void main(String[] args) { String test = "acccc"; List ans1 = subs(test); List ans2 = subsNoRepeat(test); for (String str : ans1) { System.out.println(str); } System.out.println("================="); for (String str : ans2) { System.out.println(str); } System.out.println("================="); } }
package class17; import java.util.ArrayList; import java.util.List; public class Code04_PrintAllPermutations { public static List从左往右的尝试模型 数字字符permutation1(String s) { List ans = new ArrayList<>(); if (s == null || s.length() == 0) { return ans; } char[] str = s.toCharArray(); ArrayList rest = new ArrayList (); for (char cha : str) { rest.add(cha); } String path = ""; f(rest, path, ans); return ans; } public static void f(ArrayList rest, String path, List ans) { if (rest.isEmpty()) { ans.add(path); } else { int N = rest.size(); for (int i = 0; i < N; i++) { char cur = rest.get(i); rest.remove(i); f(rest, path + cur, ans); rest.add(i, cur); } } } // 基本 public static List permutation2(String s) { List ans = new ArrayList<>(); if (s == null || s.length() == 0) { return ans; } char[] str = s.toCharArray(); g1(str, 0, ans); return ans; } public static void g1(char[] str, int index, List ans) { if (index == str.length) { ans.add(String.valueOf(str)); } else { for (int i = index; i < str.length; i++) { swap(str, index, i); g1(str, index + 1, ans); swap(str, index, i); } } } // 分支限界 public static List permutation3(String s) { List ans = new ArrayList<>(); if (s == null || s.length() == 0) { return ans; } char[] str = s.toCharArray(); g2(str, 0, ans); return ans; } public static void g2(char[] str, int index, List ans) { if (index == str.length) { ans.add(String.valueOf(str)); } else { boolean[] visited = new boolean[256]; for (int i = index; i < str.length; i++) { if (!visited[str[i]]) { visited[str[i]] = true; swap(str, index, i); g2(str, index + 1, ans); swap(str, index, i); } } } } public static void swap(char[] chs, int i, int j) { char tmp = chs[i]; chs[i] = chs[j]; chs[j] = tmp; } public static void main(String[] args) { String s = "acc"; List ans1 = permutation1(s); for (String str : ans1) { System.out.println(str); } System.out.println("======="); List ans2 = permutation2(s); for (String str : ans2) { System.out.println(str); } System.out.println("======="); List ans3 = permutation3(s); for (String str : ans3) { System.out.println(str); } } }
规定1和A对应、2和B对应、3和C对应…
那么一个数字字符串比如"111”就可以转化为:
“AAA”、"KA"和"AK"给定一个只有数字字符组成的字符串str,返回有多少种转化结果。
package class19; public class Code02_ConvertToLetterString { // str只含有数字字符0~9 // 返回多少种转化方案 public static int number(String str) { if (str == null || str.length() == 0) { return 0; } return process(str.toCharArray(), 0); } // str[0..i-1]转化无需过问 // str[i.....]去转化,返回有多少种转化方法 public static int process(char[] str, int i) { if (i == str.length) { return 1; } // i没到最后,说明有字符 if (str[i] == '0') { // 之前的决定有问题 return 0; } // str[i] != '0' // 可能性一,i单转 int ways = process(str, i + 1); if (i + 1 < str.length && (str[i] - '0') * 10 + str[i + 1] - '0' < 27) { ways += process(str, i + 2); } return ways; } // 从右往左的动态规划 // 就是上面方法的动态规划版本 // dp[i]表示:str[i...]有多少种转化方式 public static int dp1(String s) { if (s == null || s.length() == 0) { return 0; } char[] str = s.toCharArray(); int N = str.length; int[] dp = new int[N + 1]; dp[N] = 1; for (int i = N - 1; i >= 0; i--) { if (str[i] != '0') { int ways = dp[i + 1]; if (i + 1 < str.length && (str[i] - '0') * 10 + str[i + 1] - '0' < 27) { ways += dp[i + 2]; } dp[i] = ways; } } return dp[0]; } // 从左往右的动态规划 // dp[i]表示:str[0...i]有多少种转化方式 public static int dp2(String s) { if (s == null || s.length() == 0) { return 0; } char[] str = s.toCharArray(); int N = str.length; if (str[0] == '0') { return 0; } int[] dp = new int[N]; dp[0] = 1; for (int i = 1; i < N; i++) { if (str[i] == '0') { // 如果此时str[i]=='0',那么他是一定要拉前一个字符(i-1的字符)一起拼的, // 那么就要求前一个字符,不能也是‘0’,否则拼不了。 // 前一个字符不是‘0’就够了嘛?不够,还得要求拼完了要么是10,要么是20,如果更大的话,拼不了。 // 这就够了嘛?还不够,你们拼完了,还得要求str[0...i-2]真的可以被分解! // 如果str[0...i-2]都不存在分解方案,那i和i-1拼成了也不行,因为之前的搞定不了。 if (str[i - 1] == '0' || str[i - 1] > '2' || (i - 2 >= 0 && dp[i - 2] == 0)) { return 0; } else { dp[i] = i - 2 >= 0 ? dp[i - 2] : 1; } } else { dp[i] = dp[i - 1]; if (str[i - 1] != '0' && (str[i - 1] - '0') * 10 + str[i] - '0' <= 26) { dp[i] += i - 2 >= 0 ? dp[i - 2] : 1; } } } return dp[N - 1]; } // 为了测试 public static String randomString(int len) { char[] str = new char[len]; for (int i = 0; i < len; i++) { str[i] = (char) ((int) (Math.random() * 10) + '0'); } return String.valueOf(str); } // 为了测试 public static void main(String[] args) { int N = 30; int testTime = 1000000; System.out.println("测试开始"); for (int i = 0; i < testTime; i++) { int len = (int) (Math.random() * N); String s = randomString(len); int ans0 = number(s); int ans1 = dp1(s); int ans2 = dp2(s); if (ans0 != ans1 || ans0 != ans2) { System.out.println(s); System.out.println(ans0); System.out.println(ans1); System.out.println(ans2); System.out.println("Oops!"); break; } } System.out.println("测试结束"); } }背包问题
给定两个长度都为N的数组weights和values,weights[i]和values[i]分别代表 i号物品的重量和价值。给定一个正数bag,表示一个载重bag的袋子,你装的物品不能超过这个重量。返回你能装下最多的价值是多少?
package class19; public class Code01_Knapsack { // 所有的货,重量和价值,都在w和v数组里 // 为了方便,其中没有负数 // bag背包容量,不能超过这个载重 // 返回:不超重的情况下,能够得到的最大价值 public static int maxValue(int[] w, int[] v, int bag) { if (w == null || v == null || w.length != v.length || w.length == 0) { return 0; } // 尝试函数! return process(w, v, 0, bag); } // index 0~N // rest 负~bag public static int process(int[] w, int[] v, int index, int rest) { if (rest < 0) { return -1; } if (index == w.length) { return 0; } // 没要当前货,接下来的货产生的最大价值 int p1 = process(w, v, index + 1, rest); int p2 = 0; // 要了当前的货,接下来的货产生的最大价值 int next = process(w, v, index + 1, rest - w[index]); if (next != -1) { p2 = v[index] + next; } return Math.max(p1, p2); } public static int dp(int[] w, int[] v, int bag) { if (w == null || v == null || w.length != v.length || w.length == 0) { return 0; } int N = w.length; int[][] dp = new int[N + 1][bag + 1]; for (int index = N - 1; index >= 0; index--) { for (int rest = 0; rest <= bag; rest++) { int p1 = dp[index + 1][rest]; int p2 = 0; int next = rest - w[index] < 0 ? -1 : dp[index + 1][rest - w[index]]; if (next != -1) { p2 = v[index] + next; } dp[index][rest] = Math.max(p1, p2); } } return dp[0][bag]; } 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)); System.out.println(dp(weights, values, bag)); } }范围上尝试的模型 纸牌问题
给定一个整型数组arr,代表数值不同的纸牌排成一条线,玩家A和玩家B依次拿走每张纸牌,规定玩家A先拿,玩家B后拿,但是每个玩家每次只能拿走最左或最右的纸牌,玩家A和玩家B都绝顶聪明。请返回最后获胜者的分数。
package class18; public class Code02_CardsInLine { // 根据规则,返回获胜者的分数 public static int win1(int[] arr) { if (arr == null || arr.length == 0) { return 0; } int first = f1(arr, 0, arr.length - 1); int second = g1(arr, 0, arr.length - 1); return Math.max(first, second); } // arr[L..R],先手获得的最好分数返回 public static int f1(int[] arr, int L, int R) { if (L == R) { return arr[L]; } int p1 = arr[L] + g1(arr, L + 1, R); int p2 = arr[R] + g1(arr, L, R - 1); // 先手有主动权,可以拿到好的 return Math.max(p1, p2); } // // arr[L..R],后手获得的最好分数返回 public static int g1(int[] arr, int L, int R) { if (L == R) { return 0; } int p1 = f1(arr, L + 1, R); // 对手拿走了L位置的数 int p2 = f1(arr, L, R - 1); // 对手拿走了R位置的数 // 后手没有主动权,好的被别人拿了,所以只能拿到差的 return Math.min(p1, p2); } public static int win2(int[] arr) { if (arr == null || arr.length == 0) { return 0; } int N = arr.length; int[][] fmap = new int[N][N]; int[][] gmap = new int[N][N]; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { fmap[i][j] = -1; gmap[i][j] = -1; } } int first = f2(arr, 0, arr.length - 1, fmap, gmap); int second = g2(arr, 0, arr.length - 1, fmap, gmap); return Math.max(first, second); } // arr[L..R],先手获得的最好分数返回 public static int f2(int[] arr, int L, int R, int[][] fmap, int[][] gmap) { if (fmap[L][R] != -1) { return fmap[L][R]; } int ans = 0; if (L == R) { ans = arr[L]; } else { int p1 = arr[L] + g2(arr, L + 1, R, fmap, gmap); int p2 = arr[R] + g2(arr, L, R - 1, fmap, gmap); ans = Math.max(p1, p2); } fmap[L][R] = ans; return ans; } // // arr[L..R],后手获得的最好分数返回 public static int g2(int[] arr, int L, int R, int[][] fmap, int[][] gmap) { if (gmap[L][R] != -1) { return gmap[L][R]; } int ans = 0; if (L != R) { int p1 = f2(arr, L + 1, R, fmap, gmap); // 对手拿走了L位置的数 int p2 = f2(arr, L, R - 1, fmap, gmap); // 对手拿走了R位置的数 ans = Math.min(p1, p2); } gmap[L][R] = ans; return ans; } public static int win3(int[] arr) { if (arr == null || arr.length == 0) { return 0; } int N = arr.length; int[][] fmap = new int[N][N]; int[][] gmap = new int[N][N]; for (int i = 0; i < N; i++) { fmap[i][i] = arr[i]; } for (int startCol = 1; startCol < N; startCol++) { int L = 0; int R = startCol; while (R < N) { fmap[L][R] = Math.max(arr[L] + gmap[L + 1][R], arr[R] + gmap[L][R - 1]); gmap[L][R] = Math.min(fmap[L + 1][R], fmap[L][R - 1]); L++; R++; } } return Math.max(fmap[0][N - 1], gmap[0][N - 1]); } public static void main(String[] args) { int[] arr = { 5, 7, 4, 5, 8, 1, 6, 0, 3, 4, 6, 1, 7 }; System.out.println(win1(arr)); System.out.println(win2(arr)); System.out.println(win3(arr)); } }N皇后问题及位运算优化
N皇后问题是指在N*N的棋盘上要摆N个皇后,要求任何两个皇后不同行、不同列, 也不在同一条斜线上给定一个整数n,返回n皇后的摆法有多少种。
n=1,返回1,
n=2或3,2皇后和3皇后问题无论怎么摆都不行,返回0,
n=8,返回92。
package class23; public class Code03_NQueens { public static int num1(int n) { if (n < 1) { return 0; } int[] record = new int[n]; return process1(0, record, n); } // 当前来到i行,一共是0~N-1行 // 在i行上放皇后,所有列都尝试 // 必须要保证跟之前所有的皇后不打架 // int[] record record[x] = y 之前的第x行的皇后,放在了y列上 // 返回:不关心i以上发生了什么,i.... 后续有多少合法的方法数 public static int process1(int i, int[] record, int n) { if (i == n) { return 1; } int res = 0; // i行的皇后,放哪一列呢?j列, for (int j = 0; j < n; j++) { if (isValid(record, i, j)) { record[i] = j; res += process1(i + 1, record, n); } } return res; } public static boolean isValid(int[] record, int i, int j) { // 0..i-1 for (int k = 0; k < i; k++) { if (j == record[k] || Math.abs(record[k] - j) == Math.abs(i - k)) { return false; } } return true; } // 请不要超过32皇后问题 public static int num2(int n) { if (n < 1 || n > 32) { return 0; } // 如果你是13皇后问题,limit 最右13个1,其他都是0 int limit = n == 32 ? -1 : (1 << n) - 1; return process2(limit, 0, 0, 0); } // 7皇后问题 // limit : 0....0 1 1 1 1 1 1 1 // 之前皇后的列影响:colLim // 之前皇后的左下对角线影响:leftDiaLim // 之前皇后的右下对角线影响:rightDiaLim public static int process2(int limit, int colLim, int leftDiaLim, int rightDiaLim) { if (colLim == limit) { return 1; } // pos中所有是1的位置,是你可以去尝试皇后的位置 int pos = limit & (~(colLim | leftDiaLim | rightDiaLim)); int mostRightOne = 0; int res = 0; while (pos != 0) { mostRightOne = pos & (~pos + 1); pos = pos - mostRightOne; res += process2(limit, colLim | mostRightOne, (leftDiaLim | mostRightOne) << 1, (rightDiaLim | mostRightOne) >>> 1); } return res; } public static void main(String[] args) { int n = 15; long start = System.currentTimeMillis(); System.out.println(num2(n)); long end = System.currentTimeMillis(); System.out.println("cost time: " + (end - start) + "ms"); start = System.currentTimeMillis(); System.out.println(num1(n)); end = System.currentTimeMillis(); System.out.println("cost time: " + (end - start) + "ms"); } }