当前位置：首页 > news >正文

代码随想录算法训练营第二十二天| 491. 递增子序列、46. 全排列、47. 全排列Ⅱ

news 来源：原创 2024/9/19 16:07:14

今日内容

Leetcode. 491 递增子序列
Leetcode. 46 全排列
Leetcode. 47 全排列Ⅱ

Leetcode. 491 递增子序列

文章链接：代码随想录 (programmercarl.com)

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

本题也是一个子集问题，根据题意也知道要去重，提到去重就会不自觉地想到 90. 子集 II - 力扣（LeetCode）中的去重。但在本题中不能使用 Leetcode. 90 这种去重思想，因为这种去重需要对数组进行排序，而本题如果进行排序，会对得到的结果产生影响。

所以本题的去重应该用一个 Set 来记录本层已经使用过的元素。

根据上述内容，可写出代码：

class Solution {List<Integer> elem = new LinkedList<>();List<List<Integer>> result = new LinkedList<>();public List<List<Integer>> findSubsequences(int[] nums) {backtracking(nums, 0);return result;}public void backtracking(int[] nums, int startIndex){if (elem.size() >= 2){result.add(new LinkedList<>(elem));}if (startIndex == nums.length){return;}Set<Integer> used = new HashSet<>(); // 记录已使用元素的Setfor (int i = startIndex; i < nums.length; i++){if (!elem.isEmpty() && nums[i] < elem.get(elem.size() - 1) || used.contains(nums[i])){continue;}used.add(nums[i]);elem.add(nums[i]);backtracking(nums, i + 1);elem.remove(elem.size() - 1);}}
}

时间复杂度：O(n * 2 ^ n)
空间复杂度：O(n)

Leetcode. 46 全排列

文章链接：代码随想录 (programmercarl.com)

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

本题是回溯问题中的排列问题，排列问题和组合问题不同，排列问题返回得结果是有序的，比如{1, 2} {2, 1} 在排列问题中是两个不同的结果。

也正因为结果有序，所以和组合问题、分割问题以及子集问题不同，排列问题每次搜索都要从头开始，所以不需要startIndex指示下一次搜索开始的位置。

虽然排列问题不需要startIndex了，但是它返回的结果是有序的，元素的排列顺序依然需要其他变量进行标识。因此需要使用一个数组来记录每个元素的使用情况。

本题中，我们使用一个布尔数组 used 来标识每个元素的使用情况，当本层遍历使用到该元素后，该元素在used数组中的值被赋为 true。在遍历元素时，就可以根据 used 数组中对应索引的值来判断是否被使用，被使用就跳过。

排列问题经过抽象得到的树形结构图如下所示：

根据上述内容，写出如下代码：

class Solution {List<Integer> elem = new LinkedList<>();List<List<Integer>> result = new LinkedList<>();public List<List<Integer>> permute(int[] nums) {boolean[] used = new boolean[nums.length]; // 记录元素的使用情况backtracking(nums, used);return result;}public void backtracking(int[] nums, boolean[] used){if (elem.size() == nums.length){result.add(new LinkedList<>(elem));return;}for (int i = 0; i < nums.length; i++){if (used[i]){continue;} // 若元素已使用过，则跳过该元素elem.add(nums[i]);used[i] = true; // 元素被使用，赋值为truebacktracking(nums, used);used[i] = false; // 回溯elem.remove(elem.size() - 1);  }}
}

时间复杂度：O(n!)
空间复杂度：O(n)

Leetcode. 47 全排列Ⅱ

文章链接：代码随想录 (programmercarl.com)

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

本题可以看作是 Leetcode. 46 + Leetcode. 90 的结合，也就是在全排列问题中加入去重。

代码如下：

class Solution {List<Integer> elem = new LinkedList<>();List<List<Integer>> result = new LinkedList<>();public List<List<Integer>> permuteUnique(int[] nums) {boolean[] used = new boolean[nums.length];Arrays.sort(nums); // 注意一定要排序backtracking(nums, used);return result;}public void backtracking(int[] nums, boolean[] used){if (elem.size() == nums.length){result.add(new LinkedList<>(elem));return;}for (int i = 0; i < nums.length; i++){if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == true){ // 判断元素是否被使用以及去重continue;}if (used[i]){continue;}elem.add(nums[i]);used[i] = true;backtracking(nums, used);used[i] = false;elem.remove(elem.size() - 1);}}
}