注：5.1—5.3放假。
本文目录
- 491.递增子序列
- 做题
- 看文章
- 46.全排列
- 做题
- 看文章
- 47.全排列 II
- 做题
- 看文章
- 以往忽略的知识点小结
- 个人体会
491.递增子序列
代码随想录：491.递增子序列
Leetcode：491.递增子序列
做题
写了一会，但捋不出思路。可能是先找出局部最大递增序列，如何再回溯？
看文章
自己的思路有问题。首先，是在保存path时不能return，否则取不全。其次，在每层可以用set去重。看代码其实思路很简单，但就是逻辑需要梳理好。我自己理解的大概思路就是，以nums的每一个树都作为头结点，然后往下遍历，只要满足条件，加入path，就保存，否则就退出，进行下一个头结点的遍历。
还有一点：本题是求递增子序列！不是求连续递增子序列！ 之前一直在想连续的事情，还是要看好题目要求！
python">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做去重来优化。代码如下：
python">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.全排列
做题
python">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集合记录一层内使用过的数。代码如下：
python">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）。判断逻辑为：
python">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的。
完整代码如下：
python">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)
以往忽略的知识点小结
- used数组的灵活应用：替代set；树层内去重
- 出现“连续”字眼才需考虑“连续”
个人体会
完成时间：2h40min。
心得：看好题目要求；需要学会灵活使用used数组。
