代码随想录刷题day25丨491.递增子序列 ，46.全排列 ，47.全排列 II

本文主要是介绍代码随想录刷题day25丨491.递增子序列 ，46.全排列 ，47.全排列 II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

代码随想录刷题day25丨491.递增子序列 ，46.全排列 ，47.全排列 II

1.题目

1.1递增子序列

• 题目链接：491. 非递减子序列 - 力扣（LeetCode）

  

• 视频讲解：回溯算法精讲，树层去重与树枝去重 | LeetCode：491.递增子序列_哔哩哔哩_bilibili

• 文档讲解：https://programmercarl.com/0491.%E9%80%92%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97.html

• 解题思路：回溯

  • 用[4, 7, 6, 7]这个数组来举例，抽象为树形结构如图：

    

• 代码：

  class Solution {List<List<Integer>> result = new ArrayList<>();List<Integer> path = new ArrayList<>();public List<List<Integer>> findSubsequences(int[] nums) {backtracking(nums, 0);return result;}void backtracking(int[] nums, int startIndex) {if(path.size() >= 2){result.add(new ArrayList<>(path));}Set<Integer> tempSet = new HashSet<>();// 使用set对本层元素进行去重for (int i = startIndex; i < nums.length; i++) {if((!path.isEmpty() && nums[i] < path.get(path.size() - 1)) || tempSet.contains(nums[i])){continue;}tempSet.add(nums[i]);path.add(nums[i]);backtracking(nums,i + 1);path.remove(path.size() - 1);}}
  }
  

• 总结：

  • 本题求自增子序列，是不能对原数组进行排序的，排完序的数组都是自增子序列了。所以不能使用之前的去重逻辑！
  • 数组，set，map都可以做哈希表，而且数组干的活，map和set都能干，但如果数值范围小的话能用数组尽量用数组。

1.2全排列

• 题目链接：46. 全排列 - 力扣（LeetCode）

  

• 视频讲解：组合与排列的区别，回溯算法求解的时候，有何不同？| LeetCode：46.全排列_哔哩哔哩_bilibili

• 文档讲解：https://programmercarl.com/0046.%E5%85%A8%E6%8E%92%E5%88%97.html

• 解题思路：回溯

  • 以[1,2,3]为例，抽象成树形结构如下：

    

  • 回溯三部曲

    • 递归函数参数

      List<List<Integer>> result = new ArrayList<>();
      List<Integer> path = new ArrayList<>();
      void backtracking(int[] nums,boolean[] used)
      

    • 递归终止条件

      if(path.size() == nums.length){result.add(new ArrayList<>(path));return;
      }
      

    • 单层搜索的逻辑

      for(int i = 0;i < nums.length;i++){if(used[i] == true){continue;}path.add(nums[i]);used[i] = true;backtracking(nums,used);used[i] = false;path.remove(path.size() - 1);
      }
      

• 代码：

  class Solution {List<List<Integer>> result = new ArrayList<>();List<Integer> path = new ArrayList<>();public List<List<Integer>> permute(int[] nums) {boolean[] used = new boolean[nums.length];backtracking(nums,used);return result;}void backtracking(int[] nums,boolean[] used){if(path.size() == nums.length){result.add(new ArrayList<>(path));return;}for(int i = 0;i < nums.length;i++){if(used[i] == true){continue;}path.add(nums[i]);used[i] = true;backtracking(nums,used);used[i] = false;path.remove(path.size() - 1);}}
  }
  

• 总结：

  • 每层都是从0开始搜索而不是startIndex
  • 需要used数组记录path里都放了哪些元素了

1.3全排列 II

• 题目链接：47. 全排列 II - 力扣（LeetCode）

  

• 视频讲解：回溯算法求解全排列，如何去重？| LeetCode：47.全排列 II_哔哩哔哩_bilibili

• 文档讲解：https://programmercarl.com/0047.%E5%85%A8%E6%8E%92%E5%88%97II.html

• 解题思路：回溯

  • 去重一定要对元素进行排序，这样我们才方便通过相邻的节点来判断是否重复使用了。

  • 以示例中的 [1,1,2]为例 （为了方便举例，已经排序）抽象为一棵树，去重过程如图：

    

  • 图中我们对同一树层，前一位（也就是nums[i-1]）如果使用过，那么就进行去重。

• 代码：

  class Solution {List<List<Integer>> result = new ArrayList<>();List<Integer> path = new ArrayList<>();public List<List<Integer>> permuteUnique(int[] nums) {boolean[] used = new boolean[nums.length];Arrays.sort(nums);backtracking(nums, used);return result;}void backtracking(int[] nums, boolean[] used) {if (path.size() == nums.length) {result.add(new ArrayList<>(path));return;}for (int i = 0; i < nums.length; i++) {if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {continue;}if (used[i] == true) {continue;}path.add(nums[i]);used[i] = true;backtracking(nums, used);used[i] = false;path.remove(path.size() - 1);}}
  }
  

• 总结：

  • 一般来说：组合问题和排列问题是在树形结构的叶子节点上收集结果，而子集问题就是取树上所有节点的结果。

这篇关于代码随想录刷题day25丨491.递增子序列 ，46.全排列 ，47.全排列 II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---