互联斗士网站建站,苏州专业网站建设开发,做网站的天空网,深圳三合一建设网站491. 非递减子序列
题目链接#xff1a;491. 非递减子序列 - 力扣#xff08;LeetCode#xff09;
思路
1. 判断是否将当前遍历到的元素添加到path中。
如果当前元素大于等于前一个元素#xff0c;满足条件#xff0c;但前提是当前的i0#xff0c;可若加上i0…491. 非递减子序列
题目链接491. 非递减子序列 - 力扣LeetCode
思路
1. 判断是否将当前遍历到的元素添加到path中。
如果当前元素大于等于前一个元素满足条件但前提是当前的i0可若加上i0那么第一个元素就无法被加入如果一开始就将其加入之后又无法pop掉。于是想到比较当前path末尾和遍历到的数nums[i], 如果path存在且其末尾数大于nums[i]就continue到后一个数再比较。那么不满足这个if条件的数就可以加到path中。
2. 如何去重。
之前是通过将nums排序后根据当前遍历到的元素和前一个是否相同以及startIdx来去重但无法应用到此题。这里要在for循环外面建一个set来记录当前层用过的元素如果遍历到的元素出现在set里就continue到下一个。
然后我又双叒陷入到回溯的漩涡当中了......我当时认为每一次在backtracking中call自己时这个set都会被重置为空那它是如何记录的......但事实是每个递归层次的set是各自维护的在运行逻辑上会在下一层开启新的set但当回溯时还是能回到当前的set中的。
每一个for循环执行结束相当于树的一层结束每次开启新的一轮for循环时深度就会加一对当前的深度来说set重开记录当前层用过的元素。
我总是试图根据代码的逻辑一步步顺下去检验但实在有点折磨反而更容易被绕进去。最好直接从大框架上理解因为回溯的每一步都是这个大框架下类似的操作。对于set来说不要想着回溯只看一层for循环的操作我们要记录每一层用过的元素所以只要它在整个for循环外被建立每次遍历到一个元素检验其是否在set里若不在把它append到path中加到set中就可。既然对一层for循环没问题那么把放放入递归没问题。
代码实现
class Solution(object):def backtracking(self, nums, result, path, startIdx):if len(path) 1:result.append(path[:])if startIdx len(nums):returnuset set()for i in range(startIdx, len(nums)):if (path and nums[i] path[-1]) or nums[i] in uset:continuepath.append(nums[i])uset.add(nums[i])self.backtracking(nums, result, path, i1)path.pop()def findSubsequences(self, nums):result, path [], []self.backtracking(nums, result, path, 0)return result
46. 全排列
题目链接46. 全排列 - 力扣LeetCode
思路
1.不需要startIdx
设定startIdx是为了不考虑之前遍历过的元素但排列问题是有序的比如对于数组[1,2],如果要求所有集合得到[1,2]后数组的第一位到了2后面没有元素了就直接结束不用再从1开始看因为[1,2]和[2,1]是一样的。但对于排列问题它们不一样所以如果第一位遍历到2依然要考虑元素1。因此排列问题不需要startIdx。
2. 去重
我们每添加新的一位元素就要从数组第一位开始看但要跳过已经添加到path中的自己。
代码实现
class Solution(object):def backtracking(self, nums, path, result):if len(path) len(nums):result.append(path[:]) return for i in range(len(nums)):if nums[i] in path:continuepath.append(nums[i])self.backtracking(nums, path, result)path.pop()def permute(self, nums):result, path [], []self.backtracking(nums, path, result)return result47. 全排列Ⅱ
题目链接47. 全排列 II - 力扣LeetCode
思路
谨慎去重
nums包含重复数字就不能只看当前遍历到的数字在不在path里。只能对自己去重而不能去重和自己数值相同但序列和自己不同的元素。比如对于[1,1,2]我们先选1下一位从[1,1,2]开始选对于第一个1是它本身所以continue对于第二个1虽然和已有的1数值相同但因为位置不同是要加上去的。
代码实现
class Solution(object):def backtracking(self, nums, path, result, used):if len(path) len(nums):result.append(path[:])returnuset set()for i in range(len(nums)):if nums[i] in uset or used[i]:continuepath.append(nums[i])uset.add(nums[i])used[i] Trueself.backtracking(nums, path, result, used)used[i] Falsepath.pop()def permuteUnique(self, nums):path, result [], []used [False] * len(nums)self.backtracking(nums, path, result, used)return result
