算法训练营Day27(回溯3)
2024-01-02 12:26:55
39.?组合总和力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
提醒
本题是?集合里元素可以用无数次,那么和组合问题的差别?其实仅在于?startIndex上的控制
class Solution:
def combinationSum(self, candidates, target):
result = []
path=[]
candidates.sort() # 需要排序
self.backtracking(candidates, target, 0, 0, path, result)
return result
def backtracking(self, candidates, target, total, startIndex, path, result):
if total == target:
result.append(path[:])
return
for i in range(startIndex, len(candidates)):
#排序剪枝
if total + candidates[i] > target:
continue
total += candidates[i]
path.append(candidates[i])
self.backtracking(candidates, target, total, i, path, result)
total -= candidates[i]
path.pop()
40.组合总和II力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
提醒
本题开始涉及到一个问题了:去重:①树层去重②树枝去重
注意题目中给我们?集合是有重复元素的,那么求出来的?组合有可能重复,但题目要求不能有重复组合。?
注意判断是树层还是树枝
class Solution:
def backtracking(self, candidates, target, total, startIndex, used, path, result):
if total == target:
result.append(path[:])
return
?#剪枝操作(树层去重)在单层逻辑里面
for i in range(startIndex, len(candidates)):
# 对于相同的数字,只选择第一个未被使用的数字,跳过其他相同数字
if i > startIndex and candidates[i] == candidates[i - 1] and not used[i - 1]:
continue
if total + candidates[i] > target:
break
total += candidates[i]
path.append(candidates[i])
used[i] = True
self.backtracking(candidates, target, total, i + 1, used, path, result)
used[i] = False
total -= candidates[i]
path.pop()
def combinationSum2(self, candidates, target):
used = [False] * len(candidates)
result = []
candidates.sort()
self.backtracking(candidates, target, 0, 0, used, [], result)
return result
131.分割回文串力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
提醒
本题较难,大家先看视频来理解?分割问题
思考
判断回文子串为什么放在单层逻辑里,而不是放在终止条件里
如何表示切割的范围
class Solution:
def partition(self, s: str) -> List[List[str]]:
result = []
path=[]
self.backtracking(s, 0, path, result)
return result
def backtracking(self, s, start_index, path, result ):
# Base Case
if start_index == len(s):
result.append(path[:])
return
# 单层递归逻辑
for i in range(start_index, len(s)):
# 若反序和正序相同,意味着这是回文串
if s[start_index: i + 1] == s[start_index: i + 1][::-1]:
path.append(s[start_index:i+1])
# 递归纵向遍历:从下一处进行切割,判断其余是否仍为回文串
self.backtracking(s, i+1, path, result)
path.pop() # 回溯
?
文章来源:https://blog.csdn.net/2301_79788081/article/details/135210248
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!