欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 财经 > 产业 > LeetCode 第二十五天 2024.8.12

LeetCode 第二十五天 2024.8.12

2024/11/30 15:38:59 来源:https://blog.csdn.net/vvanss/article/details/141147163  浏览:    关键词:LeetCode 第二十五天 2024.8.12

1. :递增子序列
 题目链接: 491. 非递减子序列 - 力扣(LeetCode)
应用条件:回溯

难点:

这道题的难点在于如何去重,肯定不能像我们在组合中去重那样对数组排序。而且我们是要对每一层进行去重,这一点很重要。要想明白一层的意义,每一次for循环代表着一层,for循环里面的backtracking代表深度。所以在每次for循环前面设立一个set,for循环里判断现在取的这个数在不在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,i+1,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()

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com