网站结构该怎么做,哪个网站做正品女装,wordpress首页显示vip标识,模仿网站 素材哪里来1. #xff1a;递增子序列 题目链接: 491. 非递减子序列 - 力扣#xff08;LeetCode#xff09; 应用条件#xff1a;回溯
难点#xff1a;
这道题的难点在于如何去重#xff0c;肯定不能像我们在组合中去重那样对数组排序。而且我们是要对每一层进行去重#xff0c;…1. 递增子序列 题目链接: 491. 非递减子序列 - 力扣LeetCode 应用条件回溯
难点
这道题的难点在于如何去重肯定不能像我们在组合中去重那样对数组排序。而且我们是要对每一层进行去重这一点很重要。要想明白一层的意义每一次for循环代表着一层for循环里面的backtracking代表深度。所以在每次for循环前面设立一个setfor循环里判断现在取的这个数在不在set里在就不取了。这样就避免了重复问题。
个人错误
在递归中第一个判断就加了return导致输出结果少了好多。
思路
class Solution:def findSubsequences(self, nums: List[int]) - List[List[int]]:res []if len(nums) 1:return resself.backtracking(nums,0,[],res)return resdef backtracking(self,nums,startindex,cur,res):if len(cur) 2 and cur[len(cur)-1] cur[len(cur)-2]:res.append(cur[:])used set()for i in range(startindex,len(nums)):if (cur and nums[i] cur[-1]) or nums[i] in used:continueused.add(nums[i])cur.append(nums[i])self.backtracking(nums,i1,cur,res)cur.pop()2. 全排列 题目链接: 46. 全排列 - 力扣LeetCode 应用条件回溯
难点
这道题的目的是要找到数组的全排列所以我们不能有startindex这个参数但如果像上一道题那样对层去重会解决不了对树杈树的深度去重的问题例如会出现[1,1,1]这样的情况所以我们要对列去重可以直接在方法中再传入一个参数这个参数显示应该对哪个元素再列上去重再遍历完这一列后再恢复元素。
个人错误
思路
class Solution:def permute(self, nums: List[int]) - List[List[int]]:res []if len(nums) 0:return resself.backtracking(nums,[],res,[False]*len(nums))return resdef backtracking(self,nums,cur,res,used):if len(cur) len(nums):res.append(cur[:])return for i in range(len(nums)):if used[i]:continueused[i] Truecur.append(nums[i])self.backtracking(nums,cur,res,used)used[i] Falsecur.pop()
3. 全排列 II 题目链接: 47. 全排列 II - 力扣LeetCode 应用条件回溯
难点
这道题又要对层去重又要对树杈去重综合了前两道题的去重方法就可以做出来了。
个人错误
思路
class Solution:def permuteUnique(self, nums: List[int]) - List[List[int]]:res []if len(nums) 0:return resself.backtracking(nums,[],res,[False]*len(nums))return resdef backtracking(self,nums,cur,res,used):if len(cur) len(nums):res.append(cur[:])return usedd set()for i in range(len(nums)):if used[i] or (nums[i] in usedd):continueused[i] True usedd.add(nums[i])cur.append(nums[i])self.backtracking(nums,cur,res,used)used[i] Falsecur.pop()
