淘宝网站建设多少钱,中英文的网站怎么建设,家具设计师培训班,不关站备案wordpress一、第一题
找出所有相加之和为 n 的 k 个数的组合#xff0c;且满足下列条件#xff1a;
只使用数字1到9
每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次#xff0c;组合可以以任何顺序返回。示例 1:
输入: k 3, n 7
输出: [[1,…一、第一题
找出所有相加之和为 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个不同的数字我们可以得到的最小和是1234 10因为10 1没有有效的组合。
思路
代码会写了思路写不出来。。。。
代码
class Solution:def combinationSum3(self, k, n):result []res []def dfs(i, s):d k-len(res)# 等差数列,超过目标数或者剩下的全部数之和仍小于剩余需要的数s不继续递归一定是不满足条件的if s 0 or s (2*i-d1)*d//2:returnif d 0:result.append(res.copy())returnfor j in range(i, d-1, -1):res.append(j)dfs(j-1, s-j)res.pop()def dfs1(i, s):d k-len(res)if s 0 or s (2*i-d1)*d//2:returnif d 0:result.append(res.copy())# 不选iif i d:dfs(i-1, s)# 选ires.append(i)dfs(i-1, s-i)res.pop()dfs1(9, n)return resultif __name__ __main__:test Solution()n [7, 9, 1]k [3, 3, 4]for i in range(len(n)):print(test.combinationSum3(k[i], n[i]))二、第二题
给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。示例 1
输入digits 23
输出[ad,ae,af,bd,be,bf,cd,ce,cf]示例 2
输入digits
输出[]示例 3
输入digits 2
输出[a,b,c]
思路
竟然能自己写出一个。。。。。。
代码
class Solution:def letterCombinations(self, digits):给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。示例 1输入digits 23输出[ad,ae,af,bd,be,bf,cd,ce,cf]示例 2输入digits 输出[]示例 3输入digits 2输出[a,b,c]if not digits:return []result []res []re [, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz]def dfs(s):if len(s) 0:result.append(.join(res))returnelse:for i in re[int(s[0])]:res.append(i)dfs(s[1:])res.pop()dfs(digits)return resultdef letterCombinations1(self, digits):if not digits:return []result []re [, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz]def dfs(es, s):if len(s) 0:result.append(es)else:for i in re[int(s[0])]:dfs(es i, s[1:])dfs(, digits)return resultif __name__ __main__:test Solution()digits [23, , 2]for i in digits:print(test.letterCombinations(i))
