网站开发技术服务合同范本,微网站自己怎么做,园区网互联及网站建设,如何查到网站建设今日任务#xff1a; 1#xff09;216.组合总和III 2#xff09;17.电话号码的字母组合 216.组合总和III
题目链接#xff1a;216. 组合总和 III - 力扣#xff08;LeetCode#xff09; 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数#xf… 今日任务 1216.组合总和III 217.电话号码的字母组合 216.组合总和III
题目链接216. 组合总和 III - 力扣LeetCode 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数并且每种组合中不存在重复的数字。 说明 所有数字都是正整数。 解集不能包含重复的组合。 示例 1: 输入: k 3, n 7 输出: [[1,2,4]] 示例 2: 输入: k 3, n 9 输出: [[1,2,6], [1,3,5], [2,3,4]] 文章讲解代码随想录 (programmercarl.com)
视频讲解和组合问题有啥区别回溯算法如何剪枝| LeetCode216.组合总和III哔哩哔哩bilibili
思路 不难很好想采用回溯。注意细节 采用一变量历记录差值注意回溯剪枝 class Solution:def combinationSum3(self, k: int, n: int) - List[List[int]]:self.path []self.result []self.traversal(k, n, 1)return self.resultdef traversal(self, k, div, start):# 终止条件当前路径长度等于 kif len(self.path) k:# 如果剩余目标值为 0且路径长度等于 k将路径加入结果中if div 0:self.result.append(self.path[:])return# 递归层错去写法# while start div:# # 递归调用# self.path.append(start)# start 1# self.traversal(k, div - start 1, start) # div用的隐藏回溯# self.path.pop() # 回溯# 递归层for i in range(start, 10): # 从当前起始值到 9 进行遍历# 提前剪枝如果剩余目标值小于当前起始值直接返回if div i:return# 递归调用self.path.append(i)self.traversal(k, div - i, i 1) # 更新剩余目标值为 div - i起始值为 i 1self.path.pop() # 回溯
感想
代码中有一个错误写法我不能简单用差值作为遍历的终点因为数字只能1-9差值可能比9大所以后面改正了 17.电话号码的字母组合
题目链接17. 电话号码的字母组合 - 力扣LeetCode
文章讲解代码随想录 (programmercarl.com)
视频讲解还得用回溯算法| LeetCode17.电话号码的字母组合哔哩哔哩bilibili class Solution:def letterCombinations(self, digits: str) - List[str]:self.letterMap [, # 0, # 1abc, # 2def, # 3ghi, # 4jkl, # 5mno, # 6pqrs, # 7tuv, # 8wxyz # 9]self.path []self.result []if not digits:return []self.traversal(digits,0)return self.resultdef traversal(self,digits,index):if index len(digits):self.result.append(.join(self.path[:]))returnletter self.letterMap[int(digits[index])]size len(letter)for i in range(size):self.path.append(letter[i])self.traversal(digits,index1)self.path.pop()
这是没有隐藏回溯的方法
下面我们补充隐藏回溯的方法
class Solution:def letterCombinations(self, digits: str) - List[str]:# 映射每个数字对应的字符集合self.letterMap [, # 0, # 1abc, # 2def, # 3ghi, # 4jkl, # 5mno, # 6pqrs, # 7tuv, # 8wxyz # 9]self.result []if not digits:return []self.traversal(digits,0,)return self.resultdef traversal(self,digits,index,path):递归函数用于遍历数字对应的字符集合并生成组合Args:digits: 输入的数字字符串index: 当前数字的索引path: 当前已经生成的组合# 如果当前组合已经遍历完所有数字则将当前组合添加到结果列表中并返回if index len(digits):self.result.append(path)return# 获取当前数字对应的字符集合letter self.letterMap[int(digits[index])]size len(letter)# 遍历当前数字对应的字符集合for i in range(size):# 递归调用深度优先搜索函数遍历下一个数字的字符集合self.traversal(digits,index1,path letter[i])
