常见经典递归过程解析

常见经典递归过程解析

带路径的递归 vs 不带路径的递归(大部分dp，状态压缩dp认为是路径简化了结构，dp专题后续讲述)

任何递归都是dfs且非常灵活。回溯这个术语并不重要。

题目1 : 返回字符串全部子序列，子序列要求去重。时间复杂度O(2^n * n)

注: 子序列本身是可以有重复的，只是这个题目要求去重

时间复杂度:

子序列个数O(2^n) * 子序列的平均长度O(n)

• 测试链接 : https://www.nowcoder.com/practice/92e6247998294f2c933906fdedbc6e6a

• 思路1

  • 将需要操作的字符串转化为字符数组, 在字符数组中逐个处理
    • 若字符数组已经处理完毕, 说明整个字符串的一个子串已经找到, 加入set(收集每一个子串 并 去重)中即可
    • 收集当前字符
    • 递归继续处理下一个字符
    • 不收集当前字符, 将当前字符从路径中删除
    • 递归处理下一个字符
  • 将收集好的set中的数据整理返回

• 代码1

  • 	public static String[] generatePermutation1(String str) {char[] s = str.toCharArray();// 字符串转换为数组 进行操作HashSet<String> set = new HashSet<>();// 用于去重f1(s, 0, new StringBuilder(), set);// stringbuilder set 会一直往下传递// 将set中的数据 复制一份 放在String[]中按要求返回int m = set.size();String[] ans = new String[m];int i = 0;for (String cur : set) {// 从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到达了终止位置set.add(path.toString());// 路径里的信息收集到set中去} else {path.append(s[i]); // 要这个字符f1(s, i + 1, path, set);// 走递归 判断 后面位置的字符path.deleteCharAt(path.length() - 1); // 该位置 加进path的字符 从路径里 删掉f1(s, i + 1, path, set);// 字符第s[i+1]走另外一条不要i这个字符的路}}
    

• 思路2

  • 与思路1一致, 但将path改为字符串数组, 从而用覆盖操作来实现删除操作, 使删除操作更简单

• 代码2

  • 	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;}// s[i]: 当前来到的字符串里的字符  // 当前路径数组path填进来了size个字符(size就是下一个字符要放的位置)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);// 不包含这个走下一个}}
    

题目2 : 返回数组的所有组合，可以无视元素顺序。时间复杂度O(2^n * n)

时间复杂度: 最差即所有数字都不重复, 无法进行剪枝, 每一个数都分为 加入 和 不加入, 共O(2^n) 每个path长度平均为O(n), 共 O(2^n * n)

• 测试链接 : https://leetcode.cn/problems/subsets-ii/

• 思路: 剪枝

  • 先将数组排序, 按照数字进行分组, 根据每一组加入 : 0个 1个 2个 … n(该数字的个数)个, 分别往后递归加入下一组的数字

• 代码

  • 	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;}// 当前数组来到i位置	  来到的路径用size管理		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++) {// 使用for(需要用size进行限制)收集path中size个cur.add(path[j]);// 将路径加入ans}ans.add(cur);// 放入ans} else {// 没有遇到终止位置// 找下一组的开始位置int j = i + 1;while (j < nums.length && nums[i] == nums[j]) {// j 没有越界        j位置的数 等于 i位置的数j++;// j继续找}// 当前数x，要0个(size没变, path没增加)f(nums, j, path, size, ans);// 当前数x，要1个、要2个、要3个...都尝试for (; i < j; i++) {path[size++] = nums[i];// 当前的, size不断增加, path不断增加, 进行后续的递归f(nums, j, path, size, ans);// 后续的}}}
    

题目3 : 返回没有重复值数组的全部排列。时间复杂度O(n! * n)

• 测试链接 : https://leetcode.cn/problems/permutations/

• 思路

  • 在原数组中进行递归, 实现全排列
  • 当处理到数组i位置, 分别将i位置数与i + 1,i + 2 … nums.length - 1交换
  • 继续处理第i + 1位置
  • 每次处理结束后恢复数组为交换前的排列
  • 直到数组处理完毕, 复制一份加到ans中

• 代码

  • 时间复杂度: 全排列 O(n!) * 每次排列需要处理的位数, 即数组的长度O(n)

  • 	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++) {// j从i到结尾swap(nums, i, j);// 确认i位置: 将i位置的数不断修改为后续的数f(nums, i + 1, ans);// 确认!!!i+1位置, 不是j的位置swap(nums, i, j); // 复原: 将i位置的数从后续的数修改为原来的数}}// end else}public static void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}
    

题目4 : 返回可能有重复值数组的全部排列，排列要求去重。时间复杂度O(n! * n)

• 测试链接 : https://leetcode.cn/problems/permutations-ii/

• 思路

  • 在原数组中进行递归, 实现全排列
  • 当处理到数组i位置, 分别将i位置数与i + 1,i + 2 … nums.length - 1交换
    • 若当前位置的值已经与i位置交换过, 则不再进行处理, 直接进入下一次循环
  • 继续处理第i + 1位置
  • 每次处理结束后恢复数组为交换前的排列
  • 当数组处理完毕, 复制一份加到ans中

• 代码

  • 时间复杂度: 最差即为数组中没有重复值, 此时时间复杂度与题目3相同, 为 O(n! * n)

  • 	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])) {// 不能用j判断, 要用nums[j], j的值一定不同, 但是nums[j]可能重复set.add(nums[j]);swap(nums, i, j);f(nums, i + 1, ans);swap(nums, i, j);}}}// end else}public static void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}
    

题目5 : 用递归逆序一个栈。时间复杂度O(n^2)

• 思路

  • 每层递归获取并在该层保存此时栈的最后一个元素, 继续往下层递归
  • 直到栈空, 递归结束
  • 根据递归返回顺序 : 深层递归 -> 浅层递归 , 即栈底 -> 栈顶的顺序 , 保存每层栈临时保存的变量, 从而实现反转

• 代码

  • 时间复杂度

    • bottomOut: n + n - 1 + n - 2 + n - 3 + ... + 0 -> O(n^2)

  • 	// 该方法让对应递归层次保存倒序后栈中的值, 并保存在栈中, 从而实现逆序的过程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());}}
    

题目6 : 用递归排序一个栈。时间复杂度O(n^2)

• 思路

  • 计算栈的深度
  • 返回这个深度下栈的最大值
  • 返回这个深度下 这个最大值的出现次数
  • 将栈中这么多个最大值下沉
  • 递归重新计算栈的深度, 处理除掉那些最大值的数

• 代码

  • public static void sort(Stack<Integer> stack) {int deep = deep(stack);while (deep != 0) {// todo deep > 0 ?int max = max(stack,deep);int count = count(stack,deep,max);down(stack,deep,max,count);deep -= count;}}private static void down(Stack<Integer> stack, int deep, int max, int count) {if (deep == 0) {for (int i = 0; i < count; i++) {stack.push(max);}} else {int num = stack.pop();down(stack,deep - 1,max,count);if (num != max) {stack.push(num);}}}private static int count(Stack<Integer> stack, int deep, int max) {if (deep == 0) {return 0;}int num = stack.pop();int restC = count(stack, deep - 1,max);int count = restC + (num == max ? 1 : 0);stack.push(num);return count;}private 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;}private 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;}
    

题目7 : 打印n层汉诺塔问题的最优移动轨迹。时间复杂度O(2^n)

• 思路

  • 设总共有n层塔, 现将上面 n-1 层移动到中间层, 然后将第n层移动到目标层, 最后将上面 n-1 层移动到目标层即可

• 代码

  • f = f(n - 1) + 1 + f(n - 1) = 2f(n - 1) + 1 | f1 = 1 -> O(2^n)

  • 	public static void hanoi(int n) {if (n > 0) {f(n, "左", "右", "中");}}// 			将n层汉诺塔从from移动到topublic static void f(int i, String from, String to, String other) {if (i == 1) { // basecaseSystem.out.println("移动圆盘 1 从 " + from + " 到 " + to);} else {f(i - 1, from, other, to);// 移动上面i - 1个 到 other(中转)System.out.println("移动圆盘 " + i + " 从 " + from + " 到 " + to);// 将第i个移动到to(目的地)f(i - 1, other, to, from);// 移动other上i - 1个到to}}