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

zltzlt

今天的题目：

给定一个非负整数数组 nums 和一个整数 s。对于数组中的任意一个整数，都可以从 + 或 - 中选择一个符号添加在前面。

返回可以使最终数组和为 s 的所有添加符号的方法数。

示例 1：

输入：nums = [1, 1, 1, 1, 1]，s = 3
输出：5
解释：

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

一共有 5 种方法让最终和为 3。

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

蒋博文

2020-3-23 18:37:35

1. def fun358(nums,s):
   
2.     sum_nums = sum(nums)
   
3.     if sum_nums < s or (s + sum_nums) % 2 != 0:
   
4.         return 0
   
5.     result = (s + sum_nums) >> 1
   
6.     sa = [0] * (result + 1)
   
7.     sa[0] = 1
   
8.     for i in nums:
   
9.         for j in range(result, i - 1, -1):
   
10.             sa[j] += sa[j - i]
    
11.     return sa[result]

复制代码

跳转到最佳答案楼层

蒋博文

1. def fun358(nums,s):
   
2.     sum_nums = sum(nums)
   
3.     if sum_nums < s or (s + sum_nums) % 2 != 0:
   
4.         return 0
   
5.     result = (s + sum_nums) >> 1
   
6.     sa = [0] * (result + 1)
   
7.     sa[0] = 1
   
8.     for i in nums:
   
9.         for j in range(result, i - 1, -1):
   
10.             sa[j] += sa[j - i]
    
11.     return sa[result]

复制代码

kinkon

能不能多一些例子？

kinkon

貌似要用到动态规则或者递归

1. def p358(nums, s):
   
2.     a = sum(nums)
   
3.     if a < s: #nums的总和小于s无解
   
4.         return 0
   
5.     if (a + s) % 2 == 1:#nums 和 s 的总和不是偶数无解
   
6.         return 0
   
7.     """
   
8.     下面是公式:
   
9.                                  
   
10.                      s + sum(nums)  
    
11.       sum(b)= -------------------  
    
12.                            2
    
13. 
    
14.     b的位置就是求的答案
    
15.     下面很烧脑，有点绕，不好解释
    
16.     """               
    
17.     b = (a+s)//2
    
18.     m = [1]+[0]*b
    
19.     for i in nums:
    
20.         for j in range(b, i-1, -1):
    
21.             m[j] += m[j-i]
    
22. 
    
23.     return m[b]

复制代码

塔利班

暴力

1. from itertools import product as p
   
2. def f358(nums,s):
   
3.     res=0
   
4.     if sum(nums)<abs(s):
   
5.         return 0
   
6.     for e in p(*(["+-"]*len(nums))):
   
7.         if eval(''.join(a[0]+str(a[1]) for a in zip(e,nums)))==s:
   
8.             res+=1
   
9.     return res

复制代码

1. def f358(nums,s):
   
2.     def dp(a,b):
   
3.         if len(a)==1:
   
4.             return (a[0]+b,b-a[0]).count(0)
   
5.         else:
   
6.             return dp(a[1:],a[0]+b)+dp(a[1:],b-a[0])
   
7.     return dp(nums,s)

复制代码

March2615

1. # (sum(P) -sum(N)) + (sum(P) + sum(N)) = target + sum(nums)
   
2. #  -> sum(P) = (target + sun(nums)) // 2
   
3. #  -> nums中几个数之和为(target + sun(nums)) // 2 -> 背包问题
   
4. def daily358(nums: list, target: int) -> int:
   
5.     if (target + sum(nums)) % 2 != 0 or sum(nums) < target:
   
6.         return 0
   
7.     S = (target + sum(nums)) // 2
   
8.     dp = [0] * (S + 1)
   
9.     dp[0] = 1
   
10.     for num in nums:
    
11.         for j in range(S, num-1, -1):
    
12.             dp[j] += dp[j-num]
    
13.     return dp[S]
    
14. 
    
15. 
    
16. if __name__ == '__main__':
    
17.     nums = [1, 2, 3, 4]
    
18.     s = 4
    
19.     print(daily358(nums, s))

复制代码

一个账号

1. def func(nums, s) -> int:
   
2.     def dfs(cur, i, d = {}):
   
3.         if i < len(nums) and (i, cur) not in d:
   
4.             d[(i, cur)] = dfs(cur + nums[i], i + 1) + dfs(cur - nums[i], i + 1)
   
5.         return d.get((i, cur), int(cur == s))
   
6.     return dfs(0, 0)

复制代码

TJBEST

两个版本，大同小异，一个是用字典存储中间数据，一个纯递归。希望楼主都测一测，我不知道哪一个更快。

不用字典存储中间结果的版本

1. def fun358(nums,s):
   
2.     def inner(end,num):
   
3.         if end==1:
   
4.             if num != 0:
   
5.                 if nums[0]==num or nums[0]==-num:
   
6.                     return 1
   
7.                 else:
   
8.                     return 0
   
9.             else:
   
10.                 if nums[0]==0:
    
11.                     return 2
    
12.                 else:
    
13.                     return 0
    
14.         else:
    
15.             return inner(end-1,num - nums[end-1])+inner(end-1,num + nums[end-1])
    
16.     return inner(len(nums),s)

复制代码

用字典存储结果的版本

1. def fun358(nums,s):
   
2.     def inner(end,num):
   
3.         if (end,num) in dic:
   
4.             return dic[(end,num)]
   
5.         if end==1:
   
6.             if num != 0:
   
7.                 if nums[0]==num or nums[0]==-num:
   
8.                     dic[(1,num)]=1
   
9.                     return 1
   
10.                 else:
    
11.                     dic[(1,num)]=0
    
12.                     return 0
    
13.             else:
    
14.                 if nums[0]==0:
    
15.                     dic[(1,num)]=2
    
16.                     return 2
    
17.                 else:
    
18.                     dic[(1,num)]=0
    
19.                     return 0
    
20.         else:
    
21.             temp = inner(end-1,num - nums[end-1])+inner(end-1,num + nums[end-1])
    
22.             dic[(end,num)]=temp
    
23.             return temp
    
24.     dic = dict()
    
25.     return inner(len(nums),s)

复制代码

永恒的蓝色梦想

悬赏50，nb

风魔孤行者

1. def f323(nums,s):
   
2.     sums = sum(nums)
   
3.     if (sums-s)%2 == 1:
   
4.         return 0
   
5.     else:
   
6.         add = (sums-s)/2
   
7.         nums.sort()
   
8.         def f(list1,n):
   
9.             count = 0
   
10.             if n < list1[0]:
    
11.                 return 0
    
12.             elif n == list1[0]:
    
13.                 return 1
    
14.             else:
    
15.                 if f(list1[1:],n-list1[0]):
    
16.                     return count+f(list1[1:],n-list1[0])
    
17.         x = 0
    
18.         while nums != [] and add >= nums[0]:
    
19.             x += f(nums,add)
    
20.             nums = nums[1:]
    
21.         return x

复制代码

ouyunfu

挑战一行代码

1. from itertools import permutations as p
   
2. from itertools import chain as c
   
3. def f358(nums:list,s:int)->int:
   
4.     return [eval(''.join(c(*zip(i, map(str, nums))))) for i in set(p(['+','-']*len(nums),len(nums)))].count(s)

复制代码

如果是python3.8版本，可以使用海象运算符“:=”,减少一次len函数的调用，代码如下：

1. from itertools import permutations as p
   
2. from itertools import chain as c
   
3. def f358(nums:list,s:int)->int:
   
4.     return [eval(''.join(c(*zip(i, map(str, nums))))) for i in set(p(['+','-']*(L := len(nums)),L))].count(s)

复制代码

流浪的杰

我刚第二天，可能是梁静茹给我的勇气让我打开了这篇文章

fan1993423

1. def fun358(nums,s):
   
2.     if 0 in nums:
   
3.         count0=pow(2,nums.count(0))
   
4.         nums=list(filter(lambda x:x,nums))
   
5.     else:
   
6.         count0=1
   
7.     if len(nums)==1:
   
8.         if nums[0]==s or nums[0]==-s:
   
9.             return count0
   
10.         else:
    
11.             return 0
    
12.     nums.reverse()
    
13.     result=0
    
14.     def recursion(nums,s):
    
15.         nonlocal result,count0
    
16.         if len(nums)==1:
    
17.             if nums[0]==s or nums[0]==-s:
    
18.                 result+=1
    
19.                 return result
    
20.             else:
    
21.                 return result
    
22.         s+=nums[0]
    
23.         if sum(nums[1:])>s:
    
24.             recursion(nums[1:],s)+recursion(nums[1:],s-nums[0]*2)
    
25.         elif sum(nums[1:])==s:
    
26.             result+=1
    
27.             return recursion(nums[1:],s-nums[0]*2)
    
28.         else:
    
29.             return recursion(nums[1:],s-nums[0]*2)
    
30.         return result
    
31.     return recursion(nums,s)*count0

复制代码

sjtuszy

献丑一个简单的玩赖思路：

1. import random as r
   
2. 
   
3. def fun358(nums, s):
   
4.     a = len(nums)
   
5.     x = [1 for i in range(a)]
   
6.     m = n = 0
   
7.    
   
8.     while m < 10000:
   
9.         for each in range(a):
   
10.             x[each] = r.choice([-1, 1])
    
11.         if sum((nums[i]*x[i]) for i in range(a)) == s:
    
12.             n += 1
    
13.         m += 1
    
14.         
    
15.     p = (n/m) * (2 ** a)
    
16.    
    
17.     return round(p)
    

复制代码

阴阳神万物主

难度评级：中等
要素分析：算法 效率
感受：问题可以转化为对所有数字的符号做规划的二进制问题。
在时间复杂度上面，2^n  明显优于暴力破解的 n! ，而循环优于递归。
我现在在考虑要不要把贮存二进制数据的表作为一个新类去定义，直觉告诉我定义新类的话效率会更高，但是懒癌让我想到：如果已经足够了的话，就不用定义了撒。等会儿再更新作为一个新类的代码。

1. def solve(nums:'list of int>=0',s:int)->int:
   
2.     res = 0
   
3.     def bi(n):
   
4.         yield n%2
   
5.         while n := n // 2:
   
6.             yield n%2
   
7.     r = len(nums)
   
8.     for i in range(2**len(nums)):
   
9.         l = list(bi(i))
   
10.         su = 0
    
11.         for j in range(len(l)):su += nums[j] if l[j] else -nums[j]
    
12.         if su < s:continue
    
13.         while (j := j+1)<r:
    
14.             su -= nums[j]
    
15.         if su == s:
    
16.             res += 1
    
17.     return res
    
18. if __name__ == '__main__':
    
19.     print('示例 输出：',solve([1]*5,3))
    

复制代码

阴阳神万物主

这个的时间复杂度（算上定义的二进制数据自增函数）应当是 (2**n)*n

1. def solve_2(nums:'list of int>=0',s:int)->int:
   
2.     res = 0
   
3.     r = len(nums)
   
4.     class B(list):
   
5.         def __init__(self):
   
6.             list.__init__(self,(0,))
   
7.         def add(self):
   
8.             i = -1
   
9.             while 1:
   
10.                 i += 1
    
11.                 try:
    
12.                     if self[i]:self[i] = 0
    
13.                     else:self[i] += 1;return
    
14.                 except IndexError:
    
15.                     self.append(1)
    
16.                     return
    
17.     def getl():
    
18.         l = B()
    
19.         while len(l)<=r:
    
20.             yield l
    
21.             l.add()
    
22.     for l in getl():
    
23.         su = 0
    
24.         for i in range(len(l)):su += nums[i] if l[i] else -nums[i]
    
25.         if su < s:continue
    
26.         while (i := i+1)<r:
    
27.             su -= nums[i]
    
28.         if su == s:
    
29.             print(l)
    
30.             res += 1
    
31.     return res
    
32. if __name__ == '__main__':
    
33.     print('示例 输出：',solve_2([1]*5,3))

复制代码

AINIDEREN

我飘了 ，我都敢看这样的问题了

flamezyy

1. def f358(nums, s):
   
2.     if sum(nums) < abs(s):
   
3.         return 0
   
4.     elif len(nums) == 2:
   
5.         if nums[0] + nums[1] == abs(s):
   
6.             return 1
   
7.         elif abs(nums[0] - nums[1]) == abs(s):
   
8.             if s == 0:
   
9.                 return 2
   
10.             else:
    
11.                 return 1
    
12.     else:
    
13.         return f358(nums[:-1], s-nums[-1]) + f358(nums[:-1], s+nums[-1])

复制代码

先来个递归的

mdphd

1. x = [1, 1, 1, 1, 1]
   
2. s = 3
   
3. n = len(x)
   
4. ct = 0
   
5. def fh(A, B):
   
6.     if A == '1':
   
7.         return B
   
8.     if A == '0':
   
9.         return -B   
   
10. for i in range(2 ** n):
    
11.     a = bin(i)[2:].zfill(n)
    
12.     b = 0
    
13.     for j in range(n):
    
14.         b += fh(a[j], x[j])
    
15.     if b == s:
    
16.         ct += 1
    
17. print(ct)

复制代码

暴力破解
尝试优化算法遇阻，只能暴力

xiaomei47580

看到50鱼币我滚了进来。。。看大佬答题