代码随想录算法训练营Day29 | 491.递增子序列、46.全排列、47.全排列 II | Python

本文主要是介绍代码随想录算法训练营Day29 | 491.递增子序列、46.全排列、47.全排列 II | Python | 个人记录向，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

注：5.1—5.3放假。

本文目录

491.递增子序列
- 做题
- 看文章
46.全排列
- 做题
- 看文章
47.全排列 II
- 做题
- 看文章
以往忽略的知识点小结
个人体会

491.递增子序列

代码随想录：491.递增子序列
Leetcode：491.递增子序列

做题

写了一会，但捋不出思路。可能是先找出局部最大递增序列，如何再回溯？

看文章

自己的思路有问题。首先，是在保存path时不能return，否则取不全。其次，在每层可以用set去重。看代码其实思路很简单，但就是逻辑需要梳理好。我自己理解的大概思路就是，以nums的每一个树都作为头结点，然后往下遍历，只要满足条件，加入path，就保存，否则就退出，进行下一个头结点的遍历。
还有一点：本题是求递增子序列！不是求连续递增子序列！ 之前一直在想连续的事情，还是要看好题目要求！

class Solution:def findSubsequences(self, nums):result = []path = []self.backtracking(nums, 0, path, result)return resultdef backtracking(self, nums, startIndex, path, result):if len(path) > 1:result.append(path[:])  # 注意要使用切片将当前路径的副本加入结果集# 注意这里不要加return，要取树上的节点uset = set()  # 使用集合对本层元素进行去重for i in range(startIndex, len(nums)):if (path and nums[i] < path[-1]) or nums[i] in uset:continueuset.add(nums[i])  # 记录这个元素在本层用过了，本层后面不能再用了path.append(nums[i])self.backtracking(nums, i + 1, path, result)path.pop()

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

前面是用set去重，这里考虑到题目条件：-100 <= nums[i] <= 100，可以用哈希表代替set做去重来优化。代码如下：

class Solution:def findSubsequences(self, nums):result = []path = []self.backtracking(nums, 0, path, result)return resultdef backtracking(self, nums, startIndex, path, result):if len(path) > 1:result.append(path[:])  # 注意要使用切片将当前路径的副本加入结果集used = [0] * 201  # 使用数组来进行去重操作，题目说数值范围[-100, 100]for i in range(startIndex, len(nums)):if (path and nums[i] < path[-1]) or used[nums[i] + 100] == 1:continue  # 如果当前元素小于上一个元素，或者已经使用过当前元素，则跳过当前元素used[nums[i] + 100] = 1  # 标记当前元素已经使用过path.append(nums[i])  # 将当前元素加入当前递增子序列self.backtracking(nums, i + 1, path, result)path.pop()

46.全排列

代码随想录：46.全排列
Leetcode：46.全排列

做题

class Solution:def permute(self, nums: List[int]) -> List[List[int]]:self.size = len(nums)self.res = []self.path = []used = set()self.backtracking(nums, used)return self.resdef backtracking(self, nums, used):if len(self.path) == self.size:self.res.append(self.path[:])returnfor i in range(self.size):if nums[i] not in used:used.add(nums[i])self.path.append(nums[i])self.backtracking(nums, used)self.path.pop()used.remove(nums[i])

看文章

用数组代替set，可以降低空间复杂度为O(n)。
时间复杂度: O(n!)
空间复杂度: O(n)

47.全排列 II

代码随想录：47.全排列 II
Leetcode：47.全排列 II

做题

调了半小时之后AC了，使用used数组记录已经使用过的数，使用used_level集合记录一层内使用过的数。代码如下：

class Solution:def permuteUnique(self, nums: List[int]) -> List[List[int]]:self.size = len(nums)self.res = []self.path = []used = [0] * self.sizeself.backtracking(nums, used)return self.resdef backtracking(self, nums, used):if len(self.path) == self.size:self.res.append(self.path[:])returnused_level = set()for i in range(self.size):if used[i] == 0 and nums[i] not in used_level:self.path.append(nums[i])used[i] = 1used_level.add(nums[i])self.backtracking(nums, used)used[i] = 0self.path.pop()

看文章

对于树层内去重，可以仍然使用used数组（数组内遍历为bool）。判断逻辑为：

if (i > 0 and nums[i] == nums[i - 1] and not used[i - 1]) or used[i]:continue

以[1, 1, 1, 2]为例：如果已经取了nums[0]，此时used = [True, False, False, False]，那么第2层可以取nums[1]；如果没取nums[0]，此时used = [False, False, False, False]，那么第1层不能取nums[1]，因为nums[1] == nums[0]，而nums[0]已经是被append然后pop的。

完整代码如下：

class Solution:def permuteUnique(self, nums):nums.sort()  # 排序result = []self.backtracking(nums, [], [False] * len(nums), result)return resultdef backtracking(self, nums, path, used, result):if len(path) == len(nums):result.append(path[:])returnfor i in range(len(nums)):if (i > 0 and nums[i] == nums[i - 1] and not used[i - 1]) or used[i]:continueused[i] = Truepath.append(nums[i])self.backtracking(nums, path, used, result)path.pop()used[i] = False

时间复杂度: O(n! * n)。最差情况：所有元素都是唯一的，对于 n 个元素一共有 n! 中排列方案，而对于每一个答案，我们需要 O(n) 去复制最终放到 result 数组
空间复杂度: O(n)