Python：每日一题 358
今天的题目：给定一个非负整数数组 nums 和一个整数 s。对于数组中的任意一个整数，都可以从 + 或 - 中选择一个符号添加在前面。
返回可以使最终数组和为 s 的所有添加符号的方法数。
示例 1：
输入：nums = ，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。
{:10_298:}欢迎大家一起答题！{:10_298:} 本帖最后由 蒋博文 于 2020-3-24 09:58 编辑
def fun358(nums,s):
sum_nums = sum(nums)
if sum_nums < s or (s + sum_nums) % 2 != 0:
return 0
result = (s + sum_nums) >> 1
sa = * (result + 1)
sa = 1
for i in nums:
for j in range(result, i - 1, -1):
sa += sa
return sa
能不能多一些例子？ 本帖最后由 kinkon 于 2020-3-25 19:32 编辑
貌似要用到动态规则或者递归
def p358(nums, s):
a = sum(nums)
if a < s: #nums的总和小于s无解
return 0
if (a + s) % 2 == 1:#nums 和 s 的总和不是偶数无解
return 0
"""
下面是公式:
s + sum(nums)
sum(b)= -------------------
2
b的位置就是求的答案
下面很烧脑，有点绕，不好解释
"""
b = (a+s)//2
m = +*b
for i in nums:
for j in range(b, i-1, -1):
m += m
return m 本帖最后由 塔利班 于 2020-3-24 18:10 编辑
暴力
from itertools import product as p
def f358(nums,s):
res=0
if sum(nums)<abs(s):
return 0
for e in p(*(["+-"]*len(nums))):
if eval(''.join(a+str(a) for a in zip(e,nums)))==s:
res+=1
return res
def f358(nums,s):
def dp(a,b):
if len(a)==1:
return (a+b,b-a).count(0)
else:
return dp(a,a+b)+dp(a,b-a)
return dp(nums,s) 本帖最后由 March2615 于 2020-3-25 09:34 编辑
# (sum(P) -sum(N)) + (sum(P) + sum(N)) = target + sum(nums)
#-> sum(P) = (target + sun(nums)) // 2
#-> nums中几个数之和为(target + sun(nums)) // 2 -> 背包问题
def daily358(nums: list, target: int) -> int:
if (target + sum(nums)) % 2 != 0 or sum(nums) < target:
return 0
S = (target + sum(nums)) // 2
dp = * (S + 1)
dp = 1
for num in nums:
for j in range(S, num-1, -1):
dp += dp
return dp
if __name__ == '__main__':
nums =
s = 4
print(daily358(nums, s)) def func(nums, s) -> int:
def dfs(cur, i, d = {}):
if i < len(nums) and (i, cur) not in d:
d[(i, cur)] = dfs(cur + nums, i + 1) + dfs(cur - nums, i + 1)
return d.get((i, cur), int(cur == s))
return dfs(0, 0) 本帖最后由 TJBEST 于 2020-3-24 14:17 编辑
两个版本，大同小异，一个是用字典存储中间数据，一个纯递归。希望楼主都测一测，我不知道哪一个更快。
不用字典存储中间结果的版本
def fun358(nums,s):
def inner(end,num):
if end==1:
if num != 0:
if nums==num or nums==-num:
return 1
else:
return 0
else:
if nums==0:
return 2
else:
return 0
else:
return inner(end-1,num - nums)+inner(end-1,num + nums)
return inner(len(nums),s)
用字典存储结果的版本
def fun358(nums,s):
def inner(end,num):
if (end,num) in dic:
return dic[(end,num)]
if end==1:
if num != 0:
if nums==num or nums==-num:
dic[(1,num)]=1
return 1
else:
dic[(1,num)]=0
return 0
else:
if nums==0:
dic[(1,num)]=2
return 2
else:
dic[(1,num)]=0
return 0
else:
temp = inner(end-1,num - nums)+inner(end-1,num + nums)
dic[(end,num)]=temp
return temp
dic = dict()
return inner(len(nums),s) 悬赏50，nb def f323(nums,s):
sums = sum(nums)
if (sums-s)%2 == 1:
return 0
else:
add = (sums-s)/2
nums.sort()
def f(list1,n):
count = 0
if n < list1:
return 0
elif n == list1:
return 1
else:
if f(list1,n-list1):
return count+f(list1,n-list1)
x = 0
while nums != [] and add >= nums:
x += f(nums,add)
nums = nums
return x 本帖最后由 ouyunfu 于 2020-3-23 21:22 编辑
挑战一行代码from itertools import permutations as p
from itertools import chain as c
def f358(nums:list,s:int)->int:
return *len(nums),len(nums)))].count(s)
如果是python3.8版本，可以使用海象运算符“:=”,减少一次len函数的调用，代码如下：from itertools import permutations as p
from itertools import chain as c
def f358(nums:list,s:int)->int:
return *(L := len(nums)),L))].count(s)
我刚第二天，可能是梁静茹给我的勇气让我打开了这篇文章 本帖最后由 fan1993423 于 2020-3-25 18:14 编辑
def fun358(nums,s):
if 0 in nums:
count0=pow(2,nums.count(0))
nums=list(filter(lambda x:x,nums))
else:
count0=1
if len(nums)==1:
if nums==s or nums==-s:
return count0
else:
return 0
nums.reverse()
result=0
def recursion(nums,s):
nonlocal result,count0
if len(nums)==1:
if nums==s or nums==-s:
result+=1
return result
else:
return result
s+=nums
if sum(nums)>s:
recursion(nums,s)+recursion(nums,s-nums*2)
elif sum(nums)==s:
result+=1
return recursion(nums,s-nums*2)
else:
return recursion(nums,s-nums*2)
return result
return recursion(nums,s)*count0 献丑一个简单的玩赖思路：
import random as r
def fun358(nums, s):
a = len(nums)
x =
m = n = 0
while m < 10000:
for each in range(a):
x = r.choice([-1, 1])
if sum((nums*x) for i in range(a)) == s:
n += 1
m += 1
p = (n/m) * (2 ** a)
return round(p)
难度评级：中等
要素分析：算法 效率
感受：问题可以转化为对所有数字的符号做规划的二进制问题。
在时间复杂度上面，2^n明显优于暴力破解的 n! ，而循环优于递归。
我现在在考虑要不要把贮存二进制数据的表作为一个新类去定义，直觉告诉我定义新类的话效率会更高，但是懒癌让我想到：如果已经足够了的话，就不用定义了撒。等会儿再更新作为一个新类的代码。
def solve(nums:'list of int>=0',s:int)->int:
res = 0
def bi(n):
yield n%2
while n := n // 2:
yield n%2
r = len(nums)
for i in range(2**len(nums)):
l = list(bi(i))
su = 0
for j in range(len(l)):su += nums if l else -nums
if su < s:continue
while (j := j+1)<r:
su -= nums
if su == s:
res += 1
return res
if __name__ == '__main__':
print('示例 输出：',solve(*5,3))
本帖最后由 阴阳神万物主 于 2020-3-24 04:51 编辑
这个的时间复杂度（算上定义的二进制数据自增函数）应当是 (2**n)*n
def solve_2(nums:'list of int>=0',s:int)->int:
res = 0
r = len(nums)
class B(list):
def __init__(self):
list.__init__(self,(0,))
def add(self):
i = -1
while 1:
i += 1
try:
if self:self = 0
else:self += 1;return
except IndexError:
self.append(1)
return
def getl():
l = B()
while len(l)<=r:
yield l
l.add()
for l in getl():
su = 0
for i in range(len(l)):su += nums if l else -nums
if su < s:continue
while (i := i+1)<r:
su -= nums
if su == s:
print(l)
res += 1
return res
if __name__ == '__main__':
print('示例 输出：',solve_2(*5,3)) 我飘了 ，我都敢看这样的问题了
{:5_109:} 本帖最后由 flamezyy 于 2020-3-24 09:38 编辑
def f358(nums, s):
if sum(nums) < abs(s):
return 0
elif len(nums) == 2:
if nums + nums == abs(s):
return 1
elif abs(nums - nums) == abs(s):
if s == 0:
return 2
else:
return 1
else:
return f358(nums[:-1], s-nums[-1]) + f358(nums[:-1], s+nums[-1])
先来个递归的 x =
s = 3
n = len(x)
ct = 0
def fh(A, B):
if A == '1':
return B
if A == '0':
return -B
for i in range(2 ** n):
a = bin(i).zfill(n)
b = 0
for j in range(n):
b += fh(a, x)
if b == s:
ct += 1
print(ct)
暴力破解
尝试优化算法遇阻，只能暴力{:10_266:} 看到50鱼币我滚了进来。。。看大佬答题