备案控制台
开发者社区 人工智能 文章 正文

class038 经典递归解析【算法】

2023-12-21 21
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： class038 经典递归解析【算法】

class038 经典递归解析

算法讲解038【必备】常见经典递归过程解析

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);
  }
}


文章标签：
云解析DNS
算法
容器
关键词：
云解析DNS算法
解析算法
递归算法
云解析DNS递归
递归云解析DNS
日星月云
目录
相关文章
Mylvzi
|
28天前
|
算法
算法系列--递归(一)--与链表有关（上）
算法系列--递归(一)--与链表有关
Mylvzi
28 0
皮牙子抓饭
|
11天前
|
存储 机器学习/深度学习 算法
数据结构算法入门指南：常见算法解析与应用
【4月更文挑战第28天】
皮牙子抓饭
7 0
鑫宝Code
|
13天前
|
机器学习/深度学习 数据采集 人工智能
【热门话题】AI作画算法原理解析
本文解析了AI作画算法的原理，介绍了基于机器学习和深度学习的CNNs及GANs在艺术创作中的应用。从数据预处理到模型训练、优化，再到风格迁移、图像合成等实际应用，阐述了AI如何生成艺术作品。同时，文章指出未来发展中面临的版权、伦理等问题，强调理解这些算法对于探索艺术新境地的重要性。
鑫宝Code
29 3
wljslmz
|
14天前
|
存储 算法 安全
密码保护的神奇力量：对称密码算法的奥秘解析
【4月更文挑战第20天】
wljslmz
25 1
密码保护的神奇力量：对称密码算法的奥秘解析
L&ecirc;v&iuml;
|
16天前
|
存储 算法 程序员
C++从入门到精通：2.2.1标准库与STL容器算法深度解析
C++从入门到精通：2.2.1标准库与STL容器算法深度解析
L&ecirc;v&iuml;
23 0
ohh.
|
17天前
|
机器学习/深度学习 存储 人工智能
数据结构与算法设计：深度解析与实践
数据结构与算法设计：深度解析与实践
ohh.
16 0
鑫宝Code
|
22天前
|
机器学习/深度学习 数据采集 自然语言处理
【热门话题】常见分类算法解析
本文介绍了6种常见分类算法：逻辑回归、朴素贝叶斯、决策树、支持向量机、K近邻和神经网络。逻辑回归适用于线性问题，朴素贝叶斯在高维稀疏数据中有效，决策树适合规则性任务，SVM擅长小样本非线性问题，KNN对大规模数据效率低，神经网络能处理复杂任务。选择算法时需考虑数据特性、任务需求和计算资源。
鑫宝Code
25 0
阿辉不一般
|
29天前
|
搜索推荐 C语言 C++
【排序算法】C语言实现归并排序，包括递归和迭代两个版本
【排序算法】C语言实现归并排序，包括递归和迭代两个版本
阿辉不一般
13 1
简简单单做算法
|
1天前
|
存储 算法 数据可视化
基于harris角点和RANSAC算法的图像拼接matlab仿真
本文介绍了使用MATLAB2022a进行图像拼接的流程，涉及Harris角点检测和RANSAC算法。Harris角点检测寻找图像中局部曲率变化显著的点，RANSAC则用于排除噪声和异常点，找到最佳匹配。核心程序包括自定义的Harris角点计算函数，RANSAC参数设置，以及匹配点的可视化和仿射变换矩阵计算，最终生成全景图像。
简简单单做算法
9 0
我爱matlab
|
1天前
|
算法 Serverless
m基于遗传优化的LDPC码NMS译码算法最优归一化参数计算和误码率matlab仿真
MATLAB 2022a仿真实现了遗传优化的归一化最小和(NMS)译码算法，应用于低密度奇偶校验(LDPC)码。结果显示了遗传优化的迭代过程和误码率对比。遗传算法通过选择、交叉和变异操作寻找最佳归一化因子，以提升NMS译码性能。核心程序包括迭代优化、目标函数计算及性能绘图。最终，展示了SNR与误码率的关系，并保存了关键数据。
我爱matlab
11 1

热门文章

最新文章

  • 1
    【MATLAB】GA_ELM神经网络时序预测算法
  • 2
    使用Python实现DBSCAN聚类算法
  • 3
    R语言聚类算法的应用实例
  • 4
    Machine Learning机器学习之决策树算法 Decision Tree（附Python代码）
  • 5
    普林斯顿算法讲义（二）（4）
  • 6
    52个AIGC视频生成算法模型介绍（上）
  • 7
    【算法与数据结构】队列的实现详解
  • 8
    普林斯顿算法讲义（一）（4）
  • 9
    R语言贝叶斯MCMC：GLM逻辑回归、Rstan线性回归、Metropolis Hastings与Gibbs采样算法实例
  • 10
    深度学习中必备的算法：神经网络、卷积神经网络、循环神经网络
  • 1
    Java必刷入门递归题×5（内附详细递归解析图）
    26
  • 2
    【进阶C语言】数组笔试题解析
    21
  • 3
    哲学家解析Sora本质，AI视频离世界模拟器还有多远？
    32
  • 4
    HashMap源码全面解析
    43
  • 5
    Qt 5.14.2 深度解析：打造高效JSON处理利器
    46
  • 6
    机器学习的魔法（三）解析无监督学习的黑科技，揭秘新闻话题背后的神奇算法
    24
  • 7
    argparse的基本使用--参数解析
    34
  • 8
    机器学习-可解释性机器学习：随机森林与fastshap的可视化模型解析
    149
  • 9
    请描述如何使用`BeautifulSoup`或其他类似的库来解析 HTML 或 XML 数据。
    28
  • 10
    数据库核心术语解析与应用
    65

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法
  • 神经网络概览及算法详解
  • Java面试疑难点解析 - 面试技巧及语言基础
  • Java面试疑难点解析 - Java Web开发
  • Java面试疑难点解析 - 系统架构及项目设计

    • 相关电子书

    更多
  • 数据+算法定义新世界
  • 袋鼠云基于实时计算的反黄牛算法
  • Alink：基于Apache Flink的算法平台

    • 相关实验场景

    更多
  • 通过云拨测对指定服务器进行Ping/DNS监测
  • TLS1.3的后量子算法集成
  • RSA非对称加密算法

    • 推荐镜像

    更多
  • DNS
  • NTP
  • kali-security
    • 下一篇
    部署LAMP环境（Alibaba Cloud Linux 3）