公司网站建设怎么计费,网站系统繁忙是什么意思,智能建造技术,百度图在图不留网站方39. 组合总和
一开始写的时候没注意到可以重复#xff0c;注意到可以重复之后就去掉了start_index#xff0c;但是出现了类似[2,2,3][2,3,2]这种重复。看了题解之后#xff0c;发现加上start_index#xff0c;但是进for循环的时候start_index还是i#xff0c;这样就是既可…39. 组合总和
一开始写的时候没注意到可以重复注意到可以重复之后就去掉了start_index但是出现了类似[2,2,3][2,3,2]这种重复。看了题解之后发现加上start_index但是进for循环的时候start_index还是i这样就是既可以重复也不会重新取之前的数。
class Solution:def combinationSum(self, candidates: List[int], target: int) - List[List[int]]:self.res []self.backtracking(candidates, target, [], 0)return self.resdef backtracking(self, candidates, target, path, start_index):if target 0:# print(path)self.res.append(path[:])return if target 0: return for i in range(start_index, len(candidates)):if target-candidates[i] 0:continuepath.append(candidates[i])self.backtracking(candidates, target-candidates[i], path, i)path.pop()40.组合总和II
相比于之前这个题的区别就是这个在candidates里可以重复但是最后res里不能有重复的list。想要去重还挺难想的不过题解里给了一个思路就是在树的同一层进行操作即可进行去重操作。递归的时候不在树的同一层因此不需要有去重操作。
class Solution:def combinationSum2(self, candidates: List[int], target: int) - List[List[int]]:self.res []candidates.sort()self.backtracking(candidates, target, 0, [])return self.resdef backtracking(self, candidates, target, start_index, path):if target 0:self.res.append(path[:])returnfor i in range(start_index, len(candidates)):if target-candidates[i] 0: continue # 剪枝# 树的同一层如果有重复的跳过if candidates[i] candidates[i-1] and i start_index: continuepath.append(candidates[i])self.backtracking(candidates, target-candidates[i], i1, path)path.pop()131.分割回文串
这题好难。。没有思路。。根本想不到分割和回溯又什么关系。所以直接看的题解。可能需要复习复习。题解给的解释 - 递归用于纵向遍历 - for循环用于横向遍历 - 当切割线迭代至字符串末尾说明找到一种方法 - 类似组合问题为了不重复切割同一位置需要start_index来做标记下一轮递归的起始位置(切割线) - 关于模拟切割线其实就是index是上一层已经确定了的分割线i是这一层试图寻找的新分割线
class Solution:def partition(self, s: str) - List[List[str]]:self.res []self.backtracking(s, 0, [])return self.resdef backtracking(self, s, start_index, path):if start_index len(s):self.res.append(path[:])return for i in range(start_index, len(s)): # 用start_index作为分割点if self.is_palindrome(s, start_index, i):path.append(s[start_index:i1])self.backtracking(s, i1, path)path.pop()def is_palindrome(self, s, start, end):i startj endwhile(i j):if s[i] ! s[j]:return Falsei 1j - 1return True# 若反序和正序相同意味着这是回文串
if s[start_index: i 1] s[start_index: i 1][::-1]:
