代码随想录算法训练营第二十七天|第77题. 组合 216.组合总和III 17.电话号码的字母组合
第77题. 组合
给定两个整数 n 和 k,返回 1 ... n 中所有可能的 k 个数的组合。
示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
思路:
本题以学习思路为主,一开始思考了一下如何回溯,但是具体实现上和二叉树有点不同,所以没能轻易写出来,先看文字解析理解思路。附上学习传送门:
https://programmercarl.com/0077.%E7%BB%84%E5%90%88.html#%E6%80%9D%E8%B7%AF
把组合问题抽象为如下树形结构:
可以看出这棵树,一开始集合是 1,2,3,4, 从左向右取数,取过的数,不再重复取。
第一次取1,集合变为2,3,4 ,因为k为2,我们只需要再取一个数就可以了,分别取2,3,4,得到集合[1,2] [1,3] [1,4],以此类推。
每次从集合中选取元素,可选择的范围随着选择的进行而收缩,调整可选择的范围。
图中可以发现n相当于树的宽度,k相当于树的深度。
那么如何在这个树上遍历,然后收集到我们要的结果集呢?
图中每次搜索到了叶子节点,我们就找到了一个结果。
相当于只需要把达到叶子节点的结果收集起来,就可以求得 n个数中k个数的组合集合。
优化方向:剪枝
可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。
如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了,那么就没有必要搜索了。
递归三部曲:
- 参数和返回值:参数是当前开始的节点下标start和记录当前数组的列表curpath。返回值是None
- 终止条件:剪枝:如果剩下元素不足以输出完整结果,直接返回。如果当前数组列表curpath长度等于所需的k长,那么将数组压入结果中,并且返回。
- 递归逻辑:如果长度不足k长,那么继续向下遍历。从开始下标起,往后循环传入curpath数组中,然后将对下标之后的下标进行递归调用。(解释的比较混乱,建议画图理解)
根据以上思路代码实现如下:
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
self.n = n
self.k = k
self.result = []
self.visit(1, []) # 不会取0,从1开始取
return self.result
def visit(self, start:int, curpath:List[int]) -> None:
if len(curpath) == self.k:
#self.result.append(curpath) # 这里必须加[:],将curpath的整个列表加入到结果中
#如果不使用切片创建副本,那么每次添加到self.result中的curpath都是对同一个列表对象的引用。这意味着在递归过程中对curpath进行的任何修改都会反映在之前所有递归层级中添加到self.result的列表上。
self.result.append(curpath[:])
return
for i in range(start, self.n+1):
#if self.n-i < self.k-len(curpath): #确保还有足够的数字可以选择以满足剩余需要选择的数字数量
if self.n-i+1 < self.k-len(curpath):
return
curpath.append(i)
self.visit(i+1, curpath)
curpath.pop()
规范代码:
未剪枝:
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
result = [] # 存放结果集
self.backtracking(n, k, 1, [], result)
return result
def backtracking(self, n, k, startIndex, path, result):
if len(path) == k:
result.append(path[:])
return
for i in range(startIndex, n + 1): # 需要优化的地方
path.append(i) # 处理节点
self.backtracking(n, k, i + 1, path, result)
path.pop() # 回溯,撤销处理的节点
剪枝:
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
result = [] # 存放结果集
self.backtracking(n, k, 1, [], result)
return result
def backtracking(self, n, k, startIndex, path, result):
if len(path) == k:
result.append(path[:])
return
for 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 个数的组合。组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字。
说明:
- 所有数字都是正整数。
- 解集不能包含重复的组合。
示例 1: 输入: k = 3, n = 7 输出: [[1,2,4]]
示例 2: 输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]]
思路:
与前一题组合思路相似,当长度等于k时判断加和是否等于n。但剪枝部分未能成功想出来,看看文字解析是否有启发。
代码实现如下:(未剪枝)
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
self.k = k
self.n = n
self.result = []
self.visit(1, [])
return self.result
def visit(self, start:int, curpath:List[int]) -> None:
if len(curpath) == self.k:
if sum(curpath) == self.n:
self.result.append(curpath[:])
for i in range(start, 10):
curpath.append(i)
self.visit(i+1, curpath)
curpath.pop()
规范代码:(带剪枝)
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
result = [] # 存放结果集
self.backtracking(n, k, 0, 1, [], result)
return result
def backtracking(self, targetSum, k, currentSum, startIndex, path, result):
if currentSum > targetSum: # 剪枝操作
return # 如果path的长度等于k但currentSum不等于targetSum,则直接返回
if len(path) == k:
if currentSum == targetSum:
result.append(path[:])
return
for i in range(startIndex, 9 - (k - len(path)) + 2): # 剪枝
currentSum += i # 处理
path.append(i) # 处理
self.backtracking(targetSum, k, currentSum, i + 1, path, result) # 注意i+1调整startIndex
currentSum -= i # 回溯
path.pop() # 回溯
17.电话号码的字母组合
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
示例:
- 输入:"23"
- 输出:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明:尽管上面的答案是按字典序排列的,但是你可以任意选择答案输出的顺序。
思路:
回溯递归的思想很明显,但问题是如何更好完成映射,一开始只能想到字典,但后面看了一眼文字解析豁然开朗,因为输入范围是2-9,所以可以直接使用数组来进行映射。
代码实现如下:
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
self.map = ["",
"",
"abc",
"def",
"ghi",
"jkl",
"mno",
"pqrs",
"tuv",
"wxyz" ]
self.result = []
self.digits = digits
if len(digits) == 0:
return []
self.visit(0, "")
return self.result
def visit(self, index:int, curstr:str) -> None:
if index == len(self.digits):
self.result.append(curstr[:])
return
for s in self.map[int(self.digits[index])]:
curstr = curstr[:] + s
self.visit(index+1, curstr)
curstr = curstr[:-1]
规范代码:
class Solution:
def __init__(self):
self.letterMap = [
"", # 0
"", # 1
"abc", # 2
"def", # 3
"ghi", # 4
"jkl", # 5
"mno", # 6
"pqrs", # 7
"tuv", # 8
"wxyz" # 9
]
self.result = []
self.s = ""
def backtracking(self, digits, index):
if index == len(digits):
self.result.append(self.s)
return
digit = int(digits[index]) # 将索引处的数字转换为整数
letters = self.letterMap[digit] # 获取对应的字符集
for i in range(len(letters)):
self.s += letters[i] # 处理字符
self.backtracking(digits, index + 1) # 递归调用,注意索引加1,处理下一个数字
self.s = self.s[:-1] # 回溯,删除最后添加的字符
def letterCombinations(self, digits):
if len(digits) == 0:
return self.result
self.backtracking(digits, 0)
return self.result
回溯优化使用列表:
class Solution:
def __init__(self):
self.letterMap = [
"", # 0
"", # 1
"abc", # 2
"def", # 3
"ghi", # 4
"jkl", # 5
"mno", # 6
"pqrs", # 7
"tuv", # 8
"wxyz" # 9
]
def getCombinations(self, digits, index, path, result):
if index == len(digits):
result.append(''.join(path))
return
digit = int(digits[index])
letters = self.letterMap[digit]
for letter in letters:
path.append(letter)
self.getCombinations(digits, index + 1, path, result)
path.pop()
def letterCombinations(self, digits):
result = []
if len(digits) == 0:
return result
self.getCombinations(digits, 0, [], result)
return result
原文地址:https://blog.csdn.net/weixin_47681529/article/details/142737505
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!