Python：每日一题 250（答题有奖）
本帖最后由 zltzlt 于 2019-10-3 12:32 编辑今天的题目：
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：1. 所有数字都是正整数。
2. 解集不能包含重复的组合。
难度：★★☆☆☆
示例 1:
输入: k = 3, n = 7
输出: []
示例 2:
输入: k = 3, n = 9
输出: [, , ]
{:10_298:}欢迎大家一起答题！{:10_298:}
我的解法：
def combinationSum3(k: int, n: int):
from itertools import combinations as c
return list(filter(lambda x: sum(x) == n, c(range(1, 10), k))) from itertools import combinations
def kao(amount, sums):
coms = combinations(range(1, 10), amount)
return
print(kao(3, 9))
print(kao(3, 7)) 本帖最后由 panheng 于 2019-9-29 21:53 编辑
def answer(k: int, n: int):
res = []
lst =
product = list(itertools.product(lst, repeat=k))# 求笛卡尔积
for comb in product:# 筛选组合结果
if sum(comb) == n and len(set(comb)) == k:
if sorted(comb) not in res:# 剔除排列结果
res.append(list(comb))
return res kaohsing 发表于 2019-9-29 21:51
恭喜通过！
执行用时：44 ms panheng 发表于 2019-9-29 21:52
输入 k = 8, n = 36 超出内存限制 zltzlt 发表于 2019-9-29 21:56
输入 k = 8, n = 36 超出内存限制
打个补丁，用combinations方法def answer(k: int, n: int):
res = []
lst =
product = list(itertools.combinations(lst, k))
for comb in product:
if sum(comb) == n and len(set(comb)) == k:
res.append(list(comb))
return res panheng 发表于 2019-9-29 22:10
打个补丁，用combinations方法
{:10_275:}这样更省时 panheng 发表于 2019-9-29 22:10
打个补丁，用combinations方法
恭喜通过！
执行用时：48 ms 本帖最后由 jdzzj 于 2019-9-29 22:39 编辑
def combinationSum3(self, k: int, n: int) -> List]:
return
本帖最后由 angtn 于 2019-9-29 23:14 编辑
过来学习，顺便偷师{:5_109:}
from itertools import combinations
x = lambda k,n :
x(3,7)
x(3,8)
x(3,9) def solution(k: int, n: int):
def findNsum(nums, target, N, result, results):
if len(nums) < N or N < 2 or target < nums*N or target > nums[-1]*N:
return
if N == 2:
l,r = 0,len(nums)-1
while l < r:
s = nums + nums
if s == target:
results.append(result + , nums])
l += 1
while l < r and nums == nums:
l += 1
elif s < target:
l += 1
else:
r -= 1
else:
for i in range(len(nums)-N+1):
if i == 0 or (i > 0 and nums != nums):
findNsum(nums, target-nums, N-1, result+], results)
results = []
findNsum(, n, k, [], results)
return results def fun(n,k):
min=sum()
max=sum(9*10**x for x in range(k))
h=) and len(set(list(str(i))))==k]
return h 我写的长，因为没有去看官方文档，所以好多现成的工具函数不会用（之前见过也忘记了……）
效率上，我尽力了
def 求解(n, k, 当前=[], 初级=True, 结果 = []):#因为需要的最大递归深度为9 所以直接用递归
if 初级:
结果 = []
if k <= 0: #不超过0个数的组合没法相加
return []
elif n <= 0: #正整数之和不可能是非整数
return []
for i in range(1,11-k):
结果=求解(n, k-1, , False, 结果)
return 结果
else:
for i in range(max(当前[:])+1,11-k):
当前.append(i)
和 = sum(当前)
相差 = n-和
#print('调试', 结果, 当前, k, 和, n, max(当前), (相差 <= max(当前)))
if (相差) and (相差 <= max(当前)):
if 相差 < 0:
return 结果
#print('调试',当前.pop())
当前.pop()
continue
if k > 1:
if(n == 和):
return 结果
#print('调试 取下一个数', 当前)
结果=求解(n, k-1, 当前[:], False, 结果)
elif ((k == 1)and(not 相差)):
结果.append(当前)#[:])
#print('调试 结果加', 当前)
return 结果
#print('调试', 当前.pop())
当前.pop()
return 结果
if __name__ == '__main__':
print('例1 输出：',求解(7,3))
print('例2 输出：',求解(9,3))
print('自测 输出：',求解(1, 3))#不可能找出来的情况，我这里选择的是返回空列表
jdzzj 发表于 2019-9-29 22:35
恭喜通过！
执行用时：36 ms angtn 发表于 2019-9-29 23:06
过来学习，顺便偷师
恭喜通过！
执行用时：40 ms 战场原 发表于 2019-9-29 23:19
def solution(k: int, n: int):
def findNsum(nums, target, N, result, results):
if l ...
恭喜通过！
执行用时：44 ms 本帖最后由 zltzlt 于 2019-10-3 16:19 编辑
jay_jiang 发表于 2019-9-29 23:26
def fun(n,k):
min=sum()
max=sum(9*10**x for x in range(k))
解答错误
输入：k = 3, n = 7
输出：[,,,,,,,,,,,,,,,,]
预期结果：[] 阴阳神万物主 发表于 2019-9-30 01:31
我写的长，因为没有去看官方文档，所以好多现成的工具函数不会用（之前见过也忘记了……）
效率上，我尽力 ...
解答错误
输入：n = 3, k = 7
输出：[]
预期结果：[] def func(k,n):
from itertools import combinations as comb
return zltzlt 发表于 2019-9-30 18:18
解答错误
输入：n = 3, k = 7
内个，题目不是说相加之和为 n 的 k 个数的组合吗？
n = 3,k =7 时，意思不就是 7 个数的和要等于 3 吗？确实不存在啊……
页:
[1]
2