Day 28 卡玛笔记

这是基于代码随想录的每日打卡

77. 组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

输入：n = 4, k = 2
输出：
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],
]

示例 2：

输入：n = 1, k = 1
输出：[[1]]

回溯法

python">class Solution:def __init__(self):self.res=[]self.path=[]def combine(self, n: int, k: int) -> List[List[int]]:self.backtracking(n,k,1)return self.resdef backtracking(self,n,k,startIndex):# 递归终止条件if len(self.path)==k:# 在将路径添加到结果列表时，直接添加self.path会导致所有路径都指向同一个列表对象。# 在回溯过程中修改 self.path 时，之前添加到 self.res 中的路径也会被修改。self.res.append(self.path.copy())return# 递归逻辑for i in range(startIndex,n+1):self.path.append(i)self.backtracking(n,k,i+1)# 回溯self.path.pop()

运行结果

在这里插入图片描述

剪枝

python">class Solution:def __init__(self):self.res=[]self.path=[]def combine(self, n: int, k: int) -> List[List[int]]:self.backtracking(n,k,1)return self.resdef backtracking(self,n,k,startIndex):if len(self.path)==k:self.res.append(self.path.copy())return'''剪枝操作:就是剪去多余的叶子节点，根据每一层剩下多少个叶子节点来确定for循环右边的数(k-len(path))是组合还需要多少个数，比如n=4,k=3在第一层时就会剪剩下两个叶子节点（分别是1和2）那么就是n-(k-len(path))+1=2,4-(3-0)+1=2但是因为是左闭右开区间，所以要多加一个1'''for i in range(startIndex,n-(k-len(self.path))+2):self.path.append(i)self.backtracking(n,k,i+1)# 回溯self.path.pop()

运行结果

在这里插入图片描述

216. 组合总和 III

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

只使用数字1到9
每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。

示例 3:

输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。

回溯法

python">class Solution:# 剪枝1是对sum的剪枝# 剪枝2是对叶子节点的剪枝def __init__(self):# 存放结果self.res=[]# 存放路径self.path=[]def combine(self,startNum,n,k):# 剪枝1：当当前总和大于n，后面循环一定都会大于当前总和，也就是大于n，所以直接返回结果if sum(self.path)>n:return self.resif sum(self.path)==n and len(self.path)==k:self.res.append(self.path.copy())return# 剪枝2：跟上道题一样for i in range(startNum,9 - (k - len(self.path)) + 2):self.path.append(i)self.combine(i+1,n,k)self.path.pop()def combinationSum3(self, k: int, n: int) -> List[List[int]]:self.combine(1,n,k)return self.res

运行结果

在这里插入图片描述

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

输入：digits = ""
输出：[]

示例 3：

输入：digits = "2"
输出：["a","b","c"]

递归法

python">class Solution:def __init__(self):self.res=[]self.strs=''self.dig={'2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}def traversal(self,digits,index):# 递归终止条件if len(self.strs)==len(digits):self.res.append(self.strs[:])return# 递归逻辑for i in self.dig[digits[index]]:self.strs+=i# index代表当前是第几个按键index+=1self.traversal(digits,index)# 回溯self.strs=self.strs[:-1]index-=1def letterCombinations(self, digits: str) -> List[str]:if digits=='':return []# 将按键转换成列表digits=list(digits)# 传入下标为0的第一个按键self.traversal(digits,0)return self.res