[已解决]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

闲愚

1. import itertools
   
2. 
   
3. num = [7,1,2,5,1,6,10]
   
4. target = 8
   
5. summary = 0
   
6. result = []
   
7. 
   
8. for i in range(1,len(num) + 1):
   
9.     for list1 in itertools.combinations(num,i):
   
10.         for member in list1:
    
11.             summary += member
    
12.         if summary == target:
    
13.             list2 = list(list1)
    
14.             list2.sort()
    
15.             list1 = tuple(list2)
    
16.             result.append(list1)
    
17.         summary = 0
    
18. 
    
19. result = list(set(result))
    
20. print(result)
    

复制代码

晒肚皮的大青蛙

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

谢谢

华一仙

写了个低配的 DFS

1. def f280(nums, target):
   
2.     def dfs(idx, cur, target):
   
3.         if target <= 0:
   
4.             if target == 0:
   
5.                 ans.append(cur[:])
   
6.             return
   
7. 
   
8.         for i in range(idx, n):
   
9.             if target < nums[i]:  # 这条路没必要往下走，弃之
   
10.                 break
    
11.             if idx < i and nums[i-1] == nums[i]:  # 这条路之前必走过，弃之
    
12.                 continue
    
13.             cur.append(nums[i])
    
14.             dfs(i+1, cur, target-nums[i])
    
15.             cur.pop()
    
16. 
    
17.     n = len(nums)
    
18.     nums.sort()
    
19.     ans = []
    
20.     dfs(0, [], target)
    
21.     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 ' ...

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

复制代码

zltzlt

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

可能是我搞错了

晒肚皮的大青蛙

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

谢谢你