本文主要是介绍代码随想录算法训练营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)
以往忽略的知识点小结
- used数组的灵活应用:替代set;树层内去重
- 出现“连续”字眼才需考虑“连续”
个人体会
完成时间:2h40min。
心得:看好题目要求;需要学会灵活使用used数组。
这篇关于代码随想录算法训练营Day29 | 491.递增子序列、46.全排列、47.全排列 II | Python | 个人记录向的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!