论坛 › Python交流 › Python：每日一题 280

zltzlt 发表于 2019-11-26 20:48:57

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


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

zltzlt 发表于 2019-11-26 20:49:49

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

恭喜通过！

执行用时：101 ms

zltzlt 发表于 2019-11-26 20:51:11

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

恭喜通过！

执行用时：101 ms

zltzlt 发表于 2019-11-26 20:51:58

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


恭喜通过！

执行用时：101 ms

zltzlt 发表于 2019-11-26 20:53:08

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

淘专辑：https://fishc.com.cn/forum.php?mod=collection&action=view&ctid=588

zltzlt 发表于 2019-11-26 20:54:45

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


输入 num = , target = 28 超时

zltzlt 发表于 2019-11-26 20:56:14

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

def fun280(num,target):


输入 num = , target = 28 超时

zltzlt 发表于 2019-11-26 22:13:32

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

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


输入 num = , target = 5 出错：IndexError: list index out of range

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

import itertools

num =
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)

晒肚皮的大青蛙 发表于 2019-11-27 11:01:51

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

谢谢{:5_91:}

华一仙 发表于 2019-11-27 19:34:53

写了个低配的 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:# 这条路没必要往下走，弃之
                break
            if idx < i and nums == nums:# 这条路之前必走过，弃之
                continue
            cur.append(nums)
            dfs(i+1, cur, target-nums)
            cur.pop()

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

rosemary115 发表于 2019-11-27 20:34:40

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 20:55:56

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


输入 num = , target = 8 出错：AttributeError: 'NoneType' object has no attribute 'sort'

zltzlt 发表于 2019-11-27 20:56:27

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

恭喜通过！

执行用时：101 ms

zltzlt 发表于 2019-11-27 20:57:01

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




输入 num = , target = 28 超出内存限制

爱尔兰咖啡 发表于 2019-11-27 23:02:28

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

闲愚 发表于 2019-11-28 00:05:31

本帖最后由 闲愚 于 2019-11-28 00:10 编辑

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

zltzlt 发表于 2019-11-27 20:55
输入 num = , target = 8 出错：AttributeError: 'NoneType' object has no attribute ' ...

Python 3.7.0 (v3.7.0:1bf9cc5093, Jun 27 2018, 04:59:51) 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-12-22 10:39:48

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


可能是我搞错了

晒肚皮的大青蛙 发表于 2020-6-13 09:12:53

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

谢谢你{:5_91:}

查看完整版本: Python：每日一题 280