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

l0stparadise

动态规划学习中，感觉好难

1. def f358(nums,s):
   
2.     if s>sum(nums) or s<-sum(nums):
   
3.         return 0
   
4.     if (sum(nums)+s)%2:
   
5.         return 0
   
6.     else:
   
7.         real_s=int((sum(nums)+s)/2)
   
8.         dp_list=[[0]*(real_s+1) for _ in range(len(nums)) ]
   
9.         for _ in range(0,real_s+1):
   
10.             if nums[0]==_:
    
11.                 dp_list[0][_]=1
    
12.         for _ in range(0,len(nums)):
    
13.             dp_list[_][0]=1
    
14.         for i in range(1,len(nums)):
    
15.             for k in range(1,real_s+1):
    
16.                 if nums[i]<=k:
    
17.                     dp_list[i][k]=dp_list[i-1][k]+dp_list[i-1][k-nums[i]]
    
18.                 else:
    
19.                     dp_list[i][k] = dp_list[i - 1][k]
    
20. 
    
21.         return dp_list[-1][-1]

复制代码

NAMELESSONE

1. def solve(nums:list,num:int):
   
2.     num = sum(nums)-num
   
3.     if num%2 != 0:
   
4.         return 0
   
5.     target = int(num/2)
   
6.     def combinationSum2(candidates, target):
   
7.         def dfs(nums, target, start, visited, path, res):
   
8.             if target == 0:
   
9.                 res.append(path + [])
   
10.                 return
    
11.             for i in range(start, len(nums)):
    
12.                 if target - nums[i] < 0:
    
13.                     return 0
    
14.                 if i not in visited:
    
15.                     visited.add(i)
    
16.                     path.append(nums[i])
    
17.                     dfs(nums, target - nums[i], i + 1, visited, path, res)
    
18.                     path.pop()
    
19.                     visited.discard(i)        
    
20.         candidates.sort()
    
21.         res = []
    
22.         visited = set([])
    
23.         dfs(candidates, target, 0, visited, [], res)
    
24.         return res
    
25.     return len(combinationSum2(nums, target))
    
26. print(solve([1,3,4,5,1,2,3,4], 3))  

复制代码

776667

1. from itertools import permutations
   
2. 
   
3. def fun358(nums,s):
   
4.     result,n = 0,[]
   
5.     symbols = ['+' for i in range(len(nums))] + ['-' for i in range(len(nums))]
   
6.     for i in permutations(symbols,len(nums)):
   
7.         n.append(i)
   
8.     n = list(set(n))
   
9.     for i in n:
   
10.         formula = ''.join([i[j]+str(nums[j]) for j in range(len(nums))])
    
11.         if eval(formula) == s:
    
12.             result += 1
    
13.     return result

复制代码

zltzlt

kinkon 发表于 2020-3-23 19:01
貌似要用到动态规则或者递归

108 ms

zltzlt

塔利班 发表于 2020-3-23 19:45
暴力

动态规划的解答错误

输入：

1. nums = [1, 0], s = 1

复制代码

输出：1
预期结果：2

第一个超时

zltzlt

March2615 发表于 2020-3-23 20:09

80 ms

zltzlt

永恒的蓝色梦想 发表于 2020-3-23 20:37
悬赏50，nb

好久没发悬赏题了……

zltzlt

一个账号 发表于 2020-3-23 20:18

628 ms

塔利班

zltzlt 发表于 2020-3-24 17:55
动态规划的解答错误

输入：

已改

1556134029

塔利班 发表于 2020-3-23 19:45
暴力

大佬  麻烦解释一下第二段代码是啥意思

whosyourdaddy

def func358(nums,s):
    if sum(nums)<abs(s) or (s + sum(nums)) % 2 != 0:
        return 0
    def dg(a,b):
        if len(a)==1:
            return int(0 in (a[0]+b,b-a[0]))
        else:
            return dg(a[1:],b+a[0])+dg(a[1:],b-a[0])
    return dg(nums,s)

塔利班

1556134029 发表于 2020-3-24 18:11
大佬  麻烦解释一下第二段代码是啥意思

如果是长度1的Nums就检查这个数添加正负号是否=s
如果大于1，就吧第一个数单拿出来，把他和s组合到一起，然后剩下的Nums继续，如此递归直到满足长度1截止

旅途Z

import itertools
import numpy as np


def sum_equal(nums, result):
    signs = 0
    in_vector = np.array(nums)
    sign_permutations = []
    length = len(nums)
    for i in range(length):
        sign_permutations.append(1)
        sign_permutations.append(-1)
    sign_set = set(list(itertools.combinations(sign_permutations, length)))
    for sign_vector in sign_set:
        if np.dot(in_vector, np.array(sign_vector)) == result:
            signs += 1
    return signs

suchocolate

我的思路：
1）全是+号算一下：
2）全是-号算一下：
3）其他情况用排列组合出置-1 index列表，分别算出sum。

1. from itertools import combinations as cb
   
2. 
   
3. def fun358(nums, s):
   
4.     # 生成一个等长index列表
   
5.     loc = list(range(len(nums)))
   
6.     # 初始化计数器变量
   
7.     count = 0
   
8.     # 全为正值时
   
9.     if sum(nums) == s:
   
10.         count += 1
    
11.     # 全为负数时
    
12.     if 0 - sum(nums) == s:
    
13.         count += 1
    
14.     # 1到n-1个负数时
    
15.     for n in range(1, len(nums)):
    
16.         # 找出可能的组合
    
17.         cb_ls = list(cb(loc, n))
    
18.         # 循环这个组合列表，列表的元素是元组
    
19.         for x in cb_ls:
    
20.             # 复制一个nums的临时列表，用以根据index设置负数
    
21.             tmp_nm = nums.copy()
    
22.             # 循环这个元组，设置临时列表的相应位置的元素为负数
    
23.             for y in x:
    
24.                 tmp_nm[y] = -1 * tmp_nm[y]
    
25.             # 计算和，如果和等于s，那么计数器+1
    
26.             if sum(tmp_nm) == s:
    
27.                 count += 1
    
28.     return count

复制代码

ArmandXiao

1. def calculate(list_, num, result = 0, tmpList = [], length = 0):
   
2.     if not length:
   
3.       length = len(list_)  
   
4.     list_1 = list_.copy()
   
5.     result1 = result
   
6.     tmpList_ = tmpList.copy()
   
7.     tmpList1 = tmpList.copy()
   
8.     if(len(list_)>0):
   
9. 
   
10.         result += list_[0]
    
11.         tmpList_ += [list_[0]]
    
12.         if(result == num and len(tmpList_) == length):
    
13.             print(tmpList_, " = ", num)
    
14.         list_.pop(0)
    
15.         calculate(list_, num, result, tmpList_, length)
    
16. 
    
17.         result1 -= list_1[0]
    
18.         tmpList1 += [-list_1[0]]
    
19.         if(result1 == num and len(tmpList1) == length):
    
20.             print(tmpList1, " = ", num)
    
21.         list_1.pop(0)
    
22.         calculate(list_1, num, result1, tmpList1, length)

复制代码

小马爱python

kinkon 发表于 2020-3-23 19:01
貌似要用到动态规则或者递归

大神太强了可以麻烦解析一下这个算法吗

zltzlt

TJBEST 发表于 2020-3-23 20:30
两个版本，大同小异，一个是用字典存储中间数据，一个纯递归。希望楼主都测一测，我不知道哪一个更快。

...

输入 nums = [31, 4, 45, 3, 44, 49, 28, 6, 22, 24, 40, 25, 13, 46, 17, 10, 2, 38, 25, 15], s = 25 超时

zltzlt

风魔孤行者 发表于 2020-3-23 20:55

解答错误

输入：nums = [1], s = 1
输出：0
预期结果：1

zltzlt

ouyunfu 发表于 2020-3-23 21:02
挑战一行代码
如果是python3.8版本，可以使用海象运算符“:=”,减少一次len函数的调用，代码如下：

第二段代码有错哦

zltzlt

ouyunfu 发表于 2020-3-23 21:02
挑战一行代码
如果是python3.8版本，可以使用海象运算符“:=”,减少一次len函数的调用，代码如下：

第一段代码输入以下数据超时：

1. nums = [0, 0, 0, 0, 0, 0, 0, 0, 1], s = 1

复制代码