class038 经典递归解析
code1 字符串的全部子序列
// 字符串的全部子序列
// 子序列本身是可以有重复的，只是这个题目要求去重
// 测试链接 : https://www.nowcoder.com/practice/92e6247998294f2c933906fdedbc6e6a
package class038; import java.util.HashSet; // 字符串的全部子序列 // 子序列本身是可以有重复的，只是这个题目要求去重 // 测试链接 : https://www.nowcoder.com/practice/92e6247998294f2c933906fdedbc6e6a public class Code01_Subsequences { public static String[] generatePermutation1(String str) { char[] s = str.toCharArray(); HashSet<String> set = new HashSet<>(); f1(s, 0, new StringBuilder(), set); int m = set.size(); String[] ans = new String[m]; int i = 0; for (String cur : set) { ans[i++] = cur; } return ans; } // s[i...]，之前决定的路径path，set收集结果时去重 public static void f1(char[] s, int i, StringBuilder path, HashSet<String> set) { if (i == s.length) { set.add(path.toString()); } else { path.append(s[i]); // 加到路径中去 f1(s, i + 1, path, set); path.deleteCharAt(path.length() - 1); // 从路径中移除 f1(s, i + 1, path, set); } } public static String[] generatePermutation2(String str) { char[] s = str.toCharArray(); HashSet<String> set = new HashSet<>(); f2(s, 0, new char[s.length], 0, set); int m = set.size(); String[] ans = new String[m]; int i = 0; for (String cur : set) { ans[i++] = cur; } return ans; } public static void f2(char[] s, int i, char[] path, int size, HashSet<String> set) { if (i == s.length) { set.add(String.valueOf(path, 0, size)); } else { path[size] = s[i]; f2(s, i + 1, path, size + 1, set); f2(s, i + 1, path, size, set); } } }
code2 90. 子集 II
// 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的组合
// 答案 不能 包含重复的组合。返回的答案中，组合可以按 任意顺序 排列
// 注意其实要求返回的不是子集，因为子集一定是不包含相同元素的，要返回的其实是不重复的组合
// 比如输入：nums = [1,2,2]
// 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
// 测试链接 : https://leetcode.cn/problems/subsets-ii/
package class038; import java.util.ArrayList; import java.util.Arrays; import java.util.List; // 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的组合 // 答案 不能 包含重复的组合。返回的答案中，组合可以按 任意顺序 排列 // 注意其实要求返回的不是子集，因为子集一定是不包含相同元素的，要返回的其实是不重复的组合 // 比如输入：nums = [1,2,2] // 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]] // 测试链接 : https://leetcode.cn/problems/subsets-ii/ public class Code02_Combinations { public static List<List<Integer>> subsetsWithDup(int[] nums) { List<List<Integer>> ans = new ArrayList<>(); Arrays.sort(nums); f(nums, 0, new int[nums.length], 0, ans); return ans; } public static void f(int[] nums, int i, int[] path, int size, List<List<Integer>> ans) { if (i == nums.length) { ArrayList<Integer> cur = new ArrayList<>(); for (int j = 0; j < size; j++) { cur.add(path[j]); } ans.add(cur); } else { // 下一组的第一个数的位置 int j = i + 1; while (j < nums.length && nums[i] == nums[j]) { j++; } // 当前数x，要0个 f(nums, j, path, size, ans); // 当前数x，要1个、要2个、要3个...都尝试 for (; i < j; i++) { path[size++] = nums[i]; f(nums, j, path, size, ans); } } } }
code3 46. 全排列
// 没有重复项数字的全排列
// 测试链接 : https://leetcode.cn/problems/permutations/
package class038; import java.util.ArrayList; import java.util.List; // 没有重复项数字的全排列 // 测试链接 : https://leetcode.cn/problems/permutations/ public class Code03_Permutations { public static List<List<Integer>> permute(int[] nums) { List<List<Integer>> ans = new ArrayList<>(); f(nums, 0, ans); return ans; } public static void f(int[] nums, int i, List<List<Integer>> ans) { if (i == nums.length) { List<Integer> cur = new ArrayList<>(); for (int num : nums) { cur.add(num); } ans.add(cur); } else { for (int j = i; j < nums.length; j++) { swap(nums, i, j); f(nums, i + 1, ans); swap(nums, i, j); // 特别重要，课上进行了详细的图解 } } } public static void swap(int[] nums, int i, int j) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } public static void main(String[] args) { int[] nums = { 1, 2, 3 }; List<List<Integer>> ans = permute(nums); for (List<Integer> list : ans) { for (int num : list) { System.out.print(num + " "); } System.out.println(); } } }
code4 47. 全排列 II
// 有重复项数组的去重全排列
// 测试链接 : https://leetcode.cn/problems/permutations-ii/
package class038; import java.util.ArrayList; import java.util.HashSet; import java.util.List; // 有重复项数组的去重全排列 // 测试链接 : https://leetcode.cn/problems/permutations-ii/ public class Code04_PermutationWithoutRepetition { public static List<List<Integer>> permuteUnique(int[] nums) { List<List<Integer>> ans = new ArrayList<>(); f(nums, 0, ans); return ans; } public static void f(int[] nums, int i, List<List<Integer>> ans) { if (i == nums.length) { List<Integer> cur = new ArrayList<>(); for (int num : nums) { cur.add(num); } ans.add(cur); } else { HashSet<Integer> set = new HashSet<>(); for (int j = i; j < nums.length; j++) { // nums[j]没有来到过i位置，才会去尝试 if (!set.contains(nums[j])) { set.add(nums[j]); swap(nums, i, j); f(nums, i + 1, ans); swap(nums, i, j); } } } } public static void swap(int[] nums, int i, int j) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } }
code5 用递归函数逆序栈
// 用递归函数排序栈
// 栈只提供push、pop、isEmpty三个方法
// 请完成无序栈的排序，要求排完序之后，从栈顶到栈底从小到大
// 只能使用栈提供的push、pop、isEmpty三个方法、以及递归函数
// 除此之外不能使用任何的容器，数组也不行
// 就是排序过程中只能用：
// 1) 栈提供的push、pop、isEmpty三个方法
// 2) 递归函数，并且返回值最多为单个整数
package class038; import java.util.Stack; // 用递归函数逆序栈 public class Code05_ReverseStackWithRecursive { public static void reverse(Stack<Integer> stack) { if (stack.isEmpty()) { return; } int num = bottomOut(stack); reverse(stack); stack.push(num); } // 栈底元素移除掉，上面的元素盖下来 // 返回移除掉的栈底元素 public static int bottomOut(Stack<Integer> stack) { int ans = stack.pop(); if (stack.isEmpty()) { return ans; } else { int last = bottomOut(stack); stack.push(ans); return last; } } public static void main(String[] args) { Stack<Integer> stack = new Stack<Integer>(); stack.push(1); stack.push(2); stack.push(3); stack.push(4); stack.push(5); reverse(stack); while (!stack.isEmpty()) { System.out.println(stack.pop()); } } }
code6 用递归函数排序栈
// 用递归函数排序栈
// 栈只提供push、pop、isEmpty三个方法
// 请完成无序栈的排序，要求排完序之后，从栈顶到栈底从小到大
// 只能使用栈提供的push、pop、isEmpty三个方法、以及递归函数
// 除此之外不能使用任何的容器，数组也不行
// 就是排序过程中只能用：
// 1) 栈提供的push、pop、isEmpty三个方法
// 2) 递归函数，并且返回值最多为单个整数
package class038; import java.util.Stack; // 用递归函数排序栈 // 栈只提供push、pop、isEmpty三个方法 // 请完成无序栈的排序，要求排完序之后，从栈顶到栈底从小到大 // 只能使用栈提供的push、pop、isEmpty三个方法、以及递归函数 // 除此之外不能使用任何的容器，数组也不行 // 就是排序过程中只能用： // 1) 栈提供的push、pop、isEmpty三个方法 // 2) 递归函数，并且返回值最多为单个整数 public class Code06_SortStackWithRecursive { public static void sort(Stack<Integer> stack) { int deep = deep(stack); while (deep > 0) { int max = max(stack, deep); int k = times(stack, deep, max); down(stack, deep, max, k); deep -= k; } } // 返回栈的深度 // 不改变栈的数据状况 public static int deep(Stack<Integer> stack) { if (stack.isEmpty()) { return 0; } int num = stack.pop(); int deep = deep(stack) + 1; stack.push(num); return deep; } // 从栈当前的顶部开始，往下数deep层 // 返回这deep层里的最大值 public static int max(Stack<Integer> stack, int deep) { if (deep == 0) { return Integer.MIN_VALUE; } int num = stack.pop(); int restMax = max(stack, deep - 1); int max = Math.max(num, restMax); stack.push(num); return max; } // 从栈当前的顶部开始，往下数deep层，已知最大值是max了 // 返回，max出现了几次，不改变栈的数据状况 public static int times(Stack<Integer> stack, int deep, int max) { if (deep == 0) { return 0; } int num = stack.pop(); int restTimes = times(stack, deep - 1, max); int times = restTimes + (num == max ? 1 : 0); stack.push(num); return times; } // 从栈当前的顶部开始，往下数deep层，已知最大值是max，出现了k次 // 请把这k个最大值沉底，剩下的数据状况不变 public static void down(Stack<Integer> stack, int deep, int max, int k) { if (deep == 0) { for (int i = 0; i < k; i++) { stack.push(max); } } else { int num = stack.pop(); down(stack, deep - 1, max, k); if (num != max) { stack.push(num); } } } // 为了测试 // 生成随机栈 public static Stack<Integer> randomStack(int n, int v) { Stack<Integer> ans = new Stack<Integer>(); for (int i = 0; i < n; i++) { ans.add((int) (Math.random() * v)); } return ans; } // 为了测试 // 检测栈是不是从顶到底依次有序 public static boolean isSorted(Stack<Integer> stack) { int step = Integer.MIN_VALUE; while (!stack.isEmpty()) { if (step > stack.peek()) { return false; } step = stack.pop(); } return true; } // 为了测试 public static void main(String[] args) { Stack<Integer> test = new Stack<Integer>(); test.add(1); test.add(5); test.add(4); test.add(5); test.add(3); test.add(2); test.add(3); test.add(1); test.add(4); test.add(2); sort(test); while (!test.isEmpty()) { System.out.println(test.pop()); } // 随机测试 int N = 20; int V = 20; int testTimes = 20000; System.out.println("测试开始"); for (int i = 0; i < testTimes; i++) { int n = (int) (Math.random() * N); Stack<Integer> stack = randomStack(n, V); sort(stack); if (!isSorted(stack)) { System.out.println("出错了!"); break; } } System.out.println("测试结束"); } }
code7 打印n层汉诺塔问题的最优移动轨迹
// 打印n层汉诺塔问题的最优移动轨迹
package class038; // 打印n层汉诺塔问题的最优移动轨迹 public class Code07_TowerOfHanoi { public static void hanoi(int n) { if (n > 0) { f(n, "左", "右", "中"); } } public static void f(int i, String from, String to, String other) { if (i == 1) { System.out.println("移动圆盘 1 从 " + from + " 到 " + to); } else { f(i - 1, from, other, to); System.out.println("移动圆盘 " + i + " 从 " + from + " 到 " + to); f(i - 1, other, to, from); } } public static void main(String[] args) { int n = 3; hanoi(n); } }
