网站首页样式,谭谭心怎么建设网站,新浪微博登录网页版,网站建设挣钱么39. 组合总和
思路
根据题意画二叉树 这道题与之前的组合总和的区别在于#xff0c;数组中的数字可以多次使用#xff0c;因此每次递归时的startIndex依旧是从当前的i开始
尝试写代码#xff1a;
class Solution:def __init__(self):self.path []self.result []def co…39. 组合总和
思路
根据题意画二叉树 这道题与之前的组合总和的区别在于数组中的数字可以多次使用因此每次递归时的startIndex依旧是从当前的i开始
尝试写代码
class Solution:def __init__(self):self.path []self.result []def combinationSum(self, candidates: List[int], target: int) - List[List[int]]:self.backtracking(candidates, target, 0, 0)return self.resultdef backtracking(self, candidates, target, startIndex, sum):if sum target:self.result.append(self.path[:])return if sum target:returnfor i in range(startIndex, len(candidates)):sum candidates[i]self.path.append(candidates[i])self.backtracking(candidates, target, i, sum)sum - candidates[i]self.path.pop()成功通过
根据代码随想录 可以剪枝先对数组排序然后在for循环中一开始先判断当前sum 当前值是否大于目标值如果是就continue
最终代码
class Solution:def __init__(self):self.path []self.result []def combinationSum(self, candidates: List[int], target: int) - List[List[int]]:candidates.sort()self.backtracking(candidates, target, 0, 0)return self.resultdef backtracking(self, candidates, target, startIndex, sum):if sum target:self.result.append(self.path[:])return for i in range(startIndex, len(candidates)):if sum candidates[i] target:continuesum candidates[i]self.path.append(candidates[i])self.backtracking(candidates, target, i, sum)sum - candidates[i]self.path.pop()40. 组合总和 II
思路
由于给定的数组中包含重复元素最终结果可能出现重复的组合因此需要对最终结果进行去重 在python中每次得到的组合加入result之前先判断下result中是否有该组合
尝试写代码
class Solution:def __init__(self):self.path []self.result []def backtracking(self, candidates, target, startIndex, sum):if sum target:if self.path not in self.result:self.result.append(self.path[:])returnif sum target:return for i in range(startIndex, len(candidates)):sum candidates[i]self.path.append(candidates[i])self.backtracking(candidates, target, i 1, sum)sum - candidates[i]self.path.pop()def combinationSum2(self, candidates: List[int], target: int) - List[List[int]]:self.backtracking(candidates, target, 0, 0)return self.result结果不对去重失败因为每个组合的排列顺序不一样无法通过简单的in来判断。
换一种思路先排序如果i 1 i在这里进行去重 尝试写代码
class Solution:def __init__(self):self.path []self.result []def backtracking(self, candidates, target, startIndex, sum):if sum target:if self.path not in self.result:self.result.append(self.path[:])returnfor i in range(startIndex, len(candidates)):if sum candidates[i] target:continueif i - 1 and i - 1 i:continuesum candidates[i]self.path.append(candidates[i])self.backtracking(candidates, target, i 1, sum)sum - candidates[i]self.path.pop()def combinationSum2(self, candidates: List[int], target: int) - List[List[int]]:candidates.sort()self.backtracking(candidates, target, 0, 0)return self.result测试用例通过但总体超出时间限制
根据代码随想录 注意
剪枝在for循环内先判断如果sum与当前值的和大于目标值break去重如果当前值与上一个值相等continue去重时有两种方法一是i startIndex一是使用used
最终代码使用i startIndex
class Solution:def __init__(self):self.path []self.result []def backtracking(self, candidates, target, startIndex, sum):if sum target:self.result.append(self.path[:])returnfor i in range(startIndex, len(candidates)):if i startIndex and candidates[i - 1] candidates[i]:continueif sum candidates[i] target:breaksum candidates[i]self.path.append(candidates[i])self.backtracking(candidates, target, i 1, sum)sum - candidates[i]self.path.pop()def combinationSum2(self, candidates: List[int], target: int) - List[List[int]]:candidates.sort()self.backtracking(candidates, target, 0, 0)return self.result使用used
class Solution:def __init__(self):self.path []self.result []def backtracking(self, candidates, target, startIndex, sum, used):if sum target:self.result.append(self.path[:])returnfor i in range(startIndex, len(candidates)):if i 0 and candidates[i - 1] candidates[i] and not used[i - 1]:continueif sum candidates[i] target:breaksum candidates[i]self.path.append(candidates[i])used[i] Trueself.backtracking(candidates, target, i 1, sum, used)sum - candidates[i]self.path.pop()used[i] Falsedef combinationSum2(self, candidates: List[int], target: int) - List[List[int]]:used [False] * len(candidates)candidates.sort()self.backtracking(candidates, target, 0, 0, used)return self.result总结 整体思路正确但是具体写代码的去重逻辑时有错误
131. 分割回文串
思路
画出树形结构图 不知道分割在递归代码中怎么写
根据代码随想录 分割问题和组合问题非常像
要点
切割线可以用startIndex表示即终止条件是当startIndex len(s)判断回文的逻辑放在单层递归中如何表示切割的子串可以用[startIndex, i]表示切割的子串
最终代码
class Solution:def __init__(self):self.path []self.result []def isHui(self, string, start, end):while start end:if string[start] ! string[end]:return Falsestart 1end - 1return Truedef partition(self, s: str) - List[List[str]]:self.backtracking(s, 0)return self.resultdef backtracking(self, s, startIndex):if startIndex len(s):self.result.append(self.path[:])returnfor i in range(startIndex, len(s)):if self.isHui(s, startIndex, i):self.path.append(s[startIndex:i 1])else:continueself.backtracking(s, i 1)self.path.pop()
