day20-数据结构力扣

没有刚开始学习的时候热血了我也不知道我还能坚持多久39. 组合总和题目链接39. 组合总和 - 力扣LeetCode思路先贴一个我最开始写的代码超出时间限制的class Solution: def combinationSum(self, candidates: List[int], target: int) - List[List[int]]: res[] self.backtrack(candidates,target,[],res) return res def backtrack(self,candidates,target,path,res): if sum(path)target: res.append(path[:]) return for num in candidates: # 错误 1 path.append(num) self.backtrack(candidates,target-sum(path),path,res) # 错误 2、3 path.pop()错误 1每次都从头遍历 candidates →产生重复组合比如[2,3]和[3,2]都会被算进去因为你每次递归都重新从第一个数开始选。题目要求组合不看顺序[2,3] 和 [3,2] 算同一个错误 2没有判断 sum (path) target →无限递归 / 栈溢出比如 candidates[2], target1你会一直加 2 → sum2 → 超过 target 但不停止 → 死循环。错误 3每次都用 sum (path) →超级慢、效率极低递归里反复求和时间复杂度爆炸。正确做法是用减法而不是每次求和。修改class Solution: def combinationSum(self, candidates: List[int], target: int) - List[List[int]]: res [] self.backtrack(candidates, target, 0, [], res) # 加 start0 return res def backtrack(self, candidates, target, start, path, res): if target 0: # 不用 sum(path)用减法更快 res.append(path.copy()) return # 从 start 开始不回头 → 去重 for i in range(start, len(candidates)): num candidates[i] if num target: # 剪枝避免死循环 continue path.append(num) self.backtrack(candidates, target - num, i, path, res) # 传 i可重复选 path.pop()用 start 保证不回头去重用 target - num 减法高效用 if numtarget 剪枝防死循环递归传 i可重复选提交class Solution: def combinationSum(self, candidates: List[int], target: int) - List[List[int]]: res[] self.backtrack(candidates,target,0,[],res) return res def backtrack(self,candidates,target,start,path,res): if target0: res.append(path[:]) return for i in range(start,len(candidates)): numcandidates[i] if target0: return path.append(num) self.backtrack(candidates,target-num,i,path,res) path.pop()40.组合总和II题目链接40. 组合总和 II - 力扣LeetCode思路真的很绕一会不同层一会去重一会剪枝这个题和上题不同之处上一题同一个数字可以无限制重复选这一题每个数字只能用一次这一题额外candidates 里本身有重复数字要保证结果不重复第一处改动:上题可重复选# 1. 递归传 i表示还能再选当前数 self.backtrack(candidates, target - num, i, path, res)本题不能重复选# 1. 递归传 i1表示下一次只能选下一个数 self.backtrack(candidates, target - num, i1, path, res)第二处改动去重因为数组有重复数字本题# 跳过同层重复元素避免结果重复 if i start and candidates[i] candidates[i-1]: continue题目递归传什么是否要排序去重可重复选i不需要不可重复选i1需要必须排序 去重允许的重复不同层 → 纵向重复[1,1,6]禁止的重复同一层 → 横向重复[1第一个, ...]和[1第二个, ...]同层去重是为了不让结果重复提交from typing import List class Solution: def combinationSum2(self, candidates: List[int], target: int) - List[List[int]]: res [] candidates.sort() # 必须排序方便去重 self.backtrack(candidates, target, 0, [], res) return res def backtrack(self, candidates, target, start, path, res): if target 0: res.append(path.copy()) return for i in range(start, len(candidates)): num candidates[i] # 剪枝 if num target: continue # 去重关键同层不能选相同数字 if i start and candidates[i] candidates[i-1]: continue path.append(num) # 重点传 i1不能重复用当前数 self.backtrack(candidates, target - num, i 1, path, res) path.pop()131.分割回文串题目链接思路示例错误写法class Solution: def partition(self, s: str) - List[List[str]]: res[] self.backtrack(s,0,[],res) return res def backtrack(self,s,start,path,res): if path![] and pathpath[::-1]: res.append(,.join(path)) return for i in range(start,len(s)): path.append(s[i]) self.backtrack(s,i1,path,res) path.pop()判断的是整个 path是不是回文应该判断当前切的这一小段 s [start:i1]是不是回文把字符一个个加进去path.append(s[i])应该直接切一段加进去path.append(s[start:i1])提交class Solution: def partition(self, s: str): res [] self.backtrack(s, 0, [], res) return res def backtrack(self, s, start, path, res): # 切割到最后了保存答案 if start len(s): res.append(path.copy()) return # 从 start 开始切一段 for i in range(start, len(s)): substr s[start:i1] # 切一小段 # 只要这一小段是回文就继续 if substr substr[::-1]: path.append(substr) self.backtrack(s, i1, path, res) # 切后面 path.pop()