[已解决]Python：每日一题 280

zltzlt

danteer 发表于 2019-11-25 22:03

输入 num = []，target = 1 超时

zltzlt

阴阳神万物主 发表于 2019-11-25 23:18
但愿别超过最大递归深度
另外，真的不要求列表顺序哦？

恭喜通过！

执行用时：101 ms

zltzlt

Stubborn 发表于 2019-11-26 00:45
需要测试很大的数组吗？

恭喜通过！

执行用时：101 ms

zltzlt

Python3005 发表于 2019-11-26 04:04

恭喜通过！

执行用时：101 ms

zltzlt

晒肚皮的大青蛙 发表于 2019-11-26 10:52
每日一题这个系列在哪个板块找到

淘专辑：https://fishc.com.cn/forum.php?m ... n=view&ctid=588

zltzlt

776667 发表于 2019-11-26 16:51

输入 num = [29,19,14,33,11,5,9,23,23,33,12,9,25,25,12,21,14,11,20,30,17,19,5,6,6,5,5,11,12,25,31,28,31,33,27,7,33,31,17,13,21,24,17,12,6,16,20,16,22,5], target = 28 超时

zltzlt

rosemary115 发表于 2019-11-26 18:50
from itertools import combinations

def fun280(num,target):

输入 num = [29,19,14,33,11,5,9,23,23,33,12,9,25,25,12,21,14,11,20,30,17,19,5,6,6,5,5,11,12,25,31,28,31,33,27,7,33,31,17,13,21,24,17,12,6,16,20,16,22,5], target = 28 超时

zltzlt

danteer 发表于 2019-11-25 22:03
上面的大概超时，试试下面的吧 。。。

超过最大递归深度了，白给

输入 num = [9,8,7,6], target = 5 出错：IndexError: list index out of range

闲愚

import itertools

num = [7,1,2,5,1,6,10]
target = 8
summary = 0
result = []

for i in range(1,len(num) + 1):
    for list1 in itertools.combinations(num,i):
        for member in list1:
            summary += member
        if summary == target:
            list2 = list(list1)
            list2.sort()
            list1 = tuple(list2)
            result.append(list1)
        summary = 0

result = list(set(result))
print(result)

晒肚皮的大青蛙

zltzlt 发表于 2019-11-26 20:53
淘专辑：https://fishc.com.cn/forum.php?mod=collection&action=view&ctid=588

谢谢

华一仙

写了个低配的 DFS

def f280(nums, target):
    def dfs(idx, cur, target):
        if target <= 0:
            if target == 0:
                ans.append(cur[:])
            return

        for i in range(idx, n):
            if target < nums[i]:  # 这条路没必要往下走，弃之
                break
            if idx < i and nums[i-1] == nums[i]:  # 这条路之前必走过，弃之
                continue
            cur.append(nums[i])
            dfs(i+1, cur, target-nums[i])
            cur.pop()

    n = len(nums)
    nums.sort()
    ans = []
    dfs(0, [], target)
    return ans

rosemary115

import itertools


def func280(L, n):
    t, result = [], []
    for i in range(1, len(L) + 1):
        t.extend(map(tuple, map(sorted, itertools.combinations(L, i))))

    for i in set(t):
        if sum(i) == n:
            result.append(list(i))
    return result

zltzlt

闲愚 发表于 2019-11-27 00:55

输入 num = [7,1,2,5,1,6,10], target = 8 出错：AttributeError: 'NoneType' object has no attribute 'sort'

zltzlt

华一仙 发表于 2019-11-27 19:34
写了个低配的 DFS

恭喜通过！

执行用时：101 ms

zltzlt

rosemary115 发表于 2019-11-27 20:34
import itertools

输入 num = [29,19,14,33,11,5,9,23,23,33,12,9,25,25,12,21,14,11,20,30,17,19,5,6,6,5,5,11,12,25,31,28,31,33,27,7,33,31,17,13,21,24,17,12,6,16,20,16,22,5], target = 28 超出内存限制

爱尔兰咖啡

这是个排列组合问题，说下思路，具体不表了：
方案1：自定义排列组含函数（递归和非递归），求和，去重。写了个函数，一遇到大数，电脑就转不动了
方案2：使用iterertools,求和，去重
暂时没想到其他高效的算法

闲愚

闲愚

zltzlt 发表于 2019-11-27 20:55
输入 num = [7,1,2,5,1,6,10], target = 8 出错：AttributeError: 'NoneType' object has no attribute ' ...

Python 3.7.0 (v3.7.0:1bf9cc5093, Jun 27 2018, 04:59:51) [MSC v.1914 64 bit (AMD64)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> 
=================== RESTART: F:\python代码\python每日一题280.py ===================
[(1, 1, 6), (2, 6), (1, 2, 5), (1, 7)]
>>> 

zltzlt

闲愚 发表于 2019-11-28 00:07

可能是我搞错了

晒肚皮的大青蛙

zltzlt 发表于 2019-11-26 20:53
淘专辑：https://fishc.com.cn/forum.php?mod=collection&action=view&ctid=588

谢谢你