从零开始建设企业网站,网站中的滑动栏怎么做,网站建设资质证书,科技网站设计资讯216.组合总和III 文档讲解:代码随想录 题目链接#xff1a;. - 力扣#xff08;LeetCode#xff09; 这一题与昨天的组合差不多#xff0c;区别就在只有和是目标值的时候才会加入到result数组中#xff0c;并且在回溯时#xff0c;会处理sum的值
class Solution:def __i…216.组合总和III 文档讲解:代码随想录 题目链接. - 力扣LeetCode 这一题与昨天的组合差不多区别就在只有和是目标值的时候才会加入到result数组中并且在回溯时会处理sum的值
class Solution:def __init__(self):# 初始化路径self.path []# 初始化结果集self.result []def combinationSum3(self, k: int, n: int) - List[List[int]]:def backtracking(start_index, k, n, sum):# 如果路径长度等于kif len(self.path) k:# 如果路径和等于n将路径加入结果集if sum n:self.result.append(copy.deepcopy(self.path)) # 深拷贝结果return # 从[start_index, 10)范围内选择数字因为数字范围是1-9for i in range(start_index, 10):# 将当前数字加入路径self.path.append(i)# 更新路径和sum i# 递归进入下一层传入更新后的start_indexbacktracking(i1, k, n, sum)# 回溯将当前数字从路径中移除并将路径和减去当前数字sum - iself.path.pop()# 调用回溯函数起始数字从1开始backtracking(1, k, n, 0)return self.result17.电话号码的字母组合 文档讲解代码随想录 题目链接. - 力扣LeetCode 理解本题后要解决如下三个问题
数字和字母如何映射两个字母就两个for循环三个字符我就三个for循环以此类推然后发现代码根本写不出来输入1 * #按键等等异常情况
数字和字母如何映射
定义一个字符串列表列表中的每一项都是字符串下标就对应着数字
letterMap[10] [, // 0, // 1abc, // 2def, // 3ghi, // 4jkl, // 5mno, // 6pqrs, // 7tuv, // 8wxyz, // 9
]
回溯法来解决n个for循环的问题
虽然回溯算法也是暴力的但是他通过递归的方式来帮我们嵌套了我们想实现的for循环 回溯法
回溯函数参数返回值和参数
首先需要一个字符串s来收集叶子节点的结果然后用一个字符串数组result保存起来这两个变量依然定义为全局。
再来看参数参数指定是有题目中给的string digits然后还要有一个参数就是int型的index。
注意这个index可不是 77.组合 (opens new window)和216.组合总和III (opens new window)中的startIndex了。
这个index是记录遍历第几个数字了就是用来遍历digits的题目中给出数字字符串同时index也表示树的深度。之前的题目是在一个列表中求组合就不可以重复需要startindex来帮助我们避免重复这一题是在两个列表中组合所以不会有重复的
回溯函数终止条件
例如输入用例23两个数字那么根节点往下递归两层就可以了叶子节点就是要收集的结果集。
那么终止条件就是如果index 等于 输入的数字个数digits.size了本来index就是用来遍历digits的。
然后收集结果结束本层递归。 回溯搜索的单层搜索逻辑
首先要取index指向的数字并找到对应的字符集手机键盘的字符集。
然后for循环来处理这个字符集。
代码如下
class Solution:def __init__(self):# 定义全局变量self.str # 用于存储当前组合的字符串self.result [] # 用于存储所有可能的组合# 定义数字到字母的映射表self.letter_map [, # 0, # 1abc, # 2def, # 3ghi, # 4jkl, # 5mno, # 6pqrs, # 7tuv, # 8wxyz # 9]def letterCombinations(self, digits: str) - List[str]:# 将输入的数字字符串转换成列表digits list(digits)# 定义回溯函数def backtracking(digits, index):# 如果当前索引等于输入数字的长度表示已生成一个完整的组合if index len(digits):# 将当前组合的字符串深拷贝后添加到结果列表中self.result.append(self.str[:])return# 获取当前数字对应的字母集合digit int(digits[index])for i in self.letter_map[digit]:# 将当前字母添加到组合字符串中self.str i# 递归调用回溯函数处理下一个数字backtracking(digits, index 1)# 回溯移除当前添加的字母self.str self.str[:-1]# 返回最终的结果列表return self.result# 如果输入数字字符串为空直接返回空结果if len(digits) 0:return self.result# 调用回溯函数从第一个数字开始处理return backtracking(digits, 0)
