手机建站图片,网页设计入门基础知识,汽车之家网页,欧米茄手表价格官网代码随想录 - Day31 - 回溯#xff1a;组合问题
77. 组合
最容易想到的#xff1a;k层for循环。 显然不能写那么多层for循环#xff0c;所以该方法pass 使用回溯法#xff1a; 用递归解决嵌套层数的问题 n相当于树的宽度#xff0c;k相当于树的深度。 找到最深处的叶子节…代码随想录 - Day31 - 回溯组合问题
77. 组合
最容易想到的k层for循环。 显然不能写那么多层for循环所以该方法pass 使用回溯法 用递归解决嵌套层数的问题 n相当于树的宽度k相当于树的深度。 找到最深处的叶子节点即为找到一个结果把结果收集起来就是最终答案。
class Solution:def combine(self, n: int, k: int) - List[List[int]]:result [] # 存放结果集self.backtracking(n, k, 1, [], result)return resultdef backtracking(self, n, k, startIndex, path, result):if len(path) k:result.append(path[:])returnfor i in range(startIndex, n 1): # 需要优化的地方path.append(i) # 处理节点self.backtracking(n, k, i 1, path, result)path.pop() # 回溯撤销处理的节点剪枝优化 可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。 如果for循环选择的起始位置之后的元素个数已经不足需要的元素个数了那就没必要搜索了。 优化过程
已经选择的元素个数path.size();还需要的元素个数为: k - path.size();在集合n中至多要从该起始位置 : n - (k - path.size()) 1开始遍历
为什么有个1呢因为包括起始位置我们要是一个左闭的集合。
class Solution:def combine(self, n: int, k: int) - List[List[int]]:result [] # 存放结果集self.backtracking(n, k, 1, [], result)return resultdef backtracking(self, n, k, startIndex, path, result):if len(path) k:result.append(path[:])returnfor i in range(startIndex, n - (k - len(path)) 2): # 剪枝优化path.append(i) # 处理节点self.backtracking(n, k, i 1, path, result)path.pop() # 回溯撤销处理的节点216. 组合总和 III
找到和为n的k个数的组合且k在1~9之间
class Solution:def combinationSum3(self, k: int, n: int) - List[List[int]]:result [] # 存放结果集self.backtracking(n, k, 0, 1, [], result)return resultdef backtracking(self, targetSum, k, currentSum, startIndex, path, result):if currentSum targetSum: # 剪枝操作return # 如果path的长度等于k但currentSum不等于targetSum则直接返回if len(path) k and currentSum targetSum:result.append(path[:])returnfor i in range(startIndex, 10): # 剪枝优化currentSum ipath.append(i) # 处理节点self.backtracking(targetSum, k, currentSum, i 1, path, result)currentSum - ipath.pop() # 回溯撤销处理的节点剪枝优化 已选元素总和如果已经大于n了那么往后遍历就没有意义了直接剪掉。
class Solution:def combinationSum3(self, k: int, n: int) - List[List[int]]:result [] # 存放结果集self.backtracking(n, k, 0, 1, [], result)return resultdef backtracking(self, targetSum, k, currentSum, startIndex, path, result):if currentSum targetSum: # 剪枝操作return # 如果path的长度等于k但currentSum不等于targetSum则直接返回if len(path) k and currentSum targetSum:result.append(path[:])returnfor i in range(startIndex, 9 - (k - len(path)) 2): # 剪枝优化currentSum ipath.append(i) # 处理节点self.backtracking(targetSum, k, currentSum, i 1, path, result)currentSum - ipath.pop() # 回溯撤销处理的节点在一开始判断的时候不能把if currentSum targetSum写在if len(path) k里面。如果写在里面就忽略掉了currentSum targetSum len(path) ! k的情况。
17. 电话号码的字母组合
使用map或定义一个二维数组实现数字和字母的映射
def __init__(self):self.letterMap [, # 0, # 1abc, # 2def, # 3ghi, # 4jkl, # 5mno, # 6pqrs, # 7tuv, # 8wxyz # 9]self.result [] # 记录结果self.s # 字符串s来收集叶子节点的结果完整代码
class Solution:def __init__(self):self.letterMap [, # 0, # 1abc, # 2def, # 3ghi, # 4jkl, # 5mno, # 6pqrs, # 7tuv, # 8wxyz # 9]self.result []self.s []def backtracking(self, digits, index):if index len(digits):self.result.append(.join(self.s))returndigit int(digits[index])letters self.letterMap[digit]for i in range(len(letters)):self.s.append(letters[i])self.backtracking(digits, index 1)self.s.pop()def letterCombinations(self, digits: str) - List[str]:if len(digits) 0:return self.resultself.backtracking(digits, 0)return self.result由于题目中限定了2~9所以并未考虑0和1没有对应字母的情况。在实际问题中应当考虑到。
小总结
做了这几道题后发现它们的解题代码都有共通之处于是自己总结了一下。
def __init__(): # 需要的时候才写# 定义全局变量def backtracking(self, 参数1, 参数2, ...):# 回溯算法if 相等:result.append()returnfor ...:# 回溯代码self.backtracking() # 递归# 回溯代码def function():# 排除某些情况self.backtracking() # 递归return result
