本文主要是介绍【代码随想录训练营】【Day 29】【回溯-3】| Leetcode 39, 41, 131,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
【代码随想录训练营】【Day 29】【回溯-3】| Leetcode 39, 41, 131
需强化知识点
- startInex作用:一是处理是否可以有重复值,二是实现纵向遍历(不能没有)
- 去重要在数组有序的前提下进行
- 分割问题
题目
39. 组合总和
- 注意不要在for循环中乱用return,写到终止条件上,for循环中应该用break
class Solution:def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:result = []def backtracking(candidates, target, start_index, path_sum, path, result):if path_sum > target:returnif path_sum == target:result.append(path[:])returnfor i in range(start_index, len(candidates)):path_sum += candidates[i]path.append(candidates[i])backtracking(candidates, target, i, path_sum, path, result)path.pop()path_sum -= candidates[i]candidates.sort()backtracking(candidates, target, 0, 0, [], result) return result
40. 组合总和 II
- 去重:可以使用used数组,此处应该是同层不能取重复的数,used[i-1] == False,是会重复的情况
- 使用startIndex去重, i > startIndex,代表是在同层的情况,在进行横向遍历
class Solution:def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:def backtracking(result, path, target, total, candidates, startIndex):if total == target:result.append(path[:])returnfor i in range(startIndex, len(candidates)):if total + candidates[i] > target:breakif i > startIndex and candidates[i] == candidates[i-1]:continuetotal += candidates[i]path.append(candidates[i])backtracking(result, path, target, total, candidates, i+1)total -= candidates[i]path.pop()result = []candidates.sort()backtracking(result, [], target, 0, candidates, 0)return result
131. 分割回文串
- 代码随想录思路:递归用来纵向遍历,for循环用来横向遍历,切割线(就是图中的红线)切割到字符串的结尾位置,说明找到了一个切割方法。
- 再次注意,for循环内不要乱用return(此处应该为continue),继续下一种切割方案
class Solution:def partition(self, s: str) -> List[List[str]]:def isPalindrome(s):if len(s) == 1:return Trueleft, right = 0, len(s)-1while left < right:if s[left] != s[right]:return Falseleft += 1right -= 1return Truedef backtracking(s, path, result, startIndex):if startIndex == len(s):result.append(path[:])for i in range(startIndex, len(s)):select = s[startIndex:i+1]if not isPalindrome(select):continuepath.append(select)backtracking(s, path, result, i+1)path.pop()result = []backtracking(s, [], result, 0)return result
这篇关于【代码随想录训练营】【Day 29】【回溯-3】| Leetcode 39, 41, 131的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!