鱼C论坛

 找回密码
 立即注册
查看: 1571|回复: 80

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

[复制链接]
最佳答案
2807 
发表于 2020-3-23 18:37:34 | 显示全部楼层 |阅读模式
50鱼币
今天的题目:


给定一个非负整数数组 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
本帖最后由 蒋博文 于 2020-3-24 09:58 编辑
  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]
复制代码

最佳答案

查看完整内容

本帖最后由 蒋博文 于 2020-3-24 09:58 编辑

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
22 
发表于 2020-3-23 18:37:35 | 显示全部楼层    本楼为最佳答案   
本帖最后由 蒋博文 于 2020-3-24 09:58 编辑
  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荣誉 +5 鱼币 +5 收起 理由
zltzlt + 5 + 5

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
11 
发表于 2020-3-23 18:59:38 | 显示全部楼层
能不能多一些例子?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
11 
发表于 2020-3-23 19:01:55 | 显示全部楼层
本帖最后由 kinkon 于 2020-3-25 19:32 编辑

貌似要用到动态规则或者递归
  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.     b的位置就是求的答案
  14.     下面很烧脑,有点绕,不好解释
  15.     """               
  16.     b = (a+s)//2
  17.     m = [1]+[0]*b
  18.     for i in nums:
  19.         for j in range(b, i-1, -1):
  20.             m[j] += m[j-i]

  21.     return m[b]
复制代码

评分

参与人数 1荣誉 +5 鱼币 +5 收起 理由
zltzlt + 5 + 5

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
1801 
发表于 2020-3-23 19:45:32 | 显示全部楼层
本帖最后由 塔利班 于 2020-3-24 18:10 编辑

暴力
  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)
复制代码

评分

参与人数 1荣誉 +3 鱼币 +3 收起 理由
zltzlt + 3 + 3

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
7 
发表于 2020-3-23 20:09:40 | 显示全部楼层
本帖最后由 March2615 于 2020-3-25 09:34 编辑
  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. if __name__ == '__main__':
  15.     nums = [1, 2, 3, 4]
  16.     s = 4
  17.     print(daily358(nums, s))
复制代码

评分

参与人数 1荣誉 +5 鱼币 +5 收起 理由
zltzlt + 5 + 5

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
234 
发表于 2020-3-23 20:18:22 | 显示全部楼层
  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)
复制代码

评分

参与人数 2荣誉 +5 鱼币 +5 收起 理由
whx2008 + 1 + 1 666
zltzlt + 4 + 4

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
33 
发表于 2020-3-23 20:30:49 | 显示全部楼层
本帖最后由 TJBEST 于 2020-3-24 14:17 编辑

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

不用字典存储中间结果的版本
  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)
复制代码

评分

参与人数 1荣誉 +3 鱼币 +3 收起 理由
zltzlt + 3 + 3

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
453 
发表于 2020-3-23 20:37:42 | 显示全部楼层
悬赏50,nb
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
1 
发表于 2020-3-23 20:55:36 | 显示全部楼层
  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
复制代码

评分

参与人数 1荣誉 +3 鱼币 +3 收起 理由
zltzlt + 3 + 3

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
57 
发表于 2020-3-23 21:02:39 | 显示全部楼层
本帖最后由 ouyunfu 于 2020-3-23 21:22 编辑

挑战一行代码
  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)
复制代码


评分

参与人数 1荣誉 +3 鱼币 +3 收起 理由
zltzlt + 3 + 3

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 2020-3-23 21:38:59 | 显示全部楼层
我刚第二天,可能是梁静茹给我的勇气让我打开了这篇文章
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
28 
发表于 2020-3-23 21:49:20 | 显示全部楼层
本帖最后由 fan1993423 于 2020-3-25 18:14 编辑
  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
复制代码

评分

参与人数 1荣誉 +3 鱼币 +3 收起 理由
zltzlt + 3 + 3

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 2020-3-23 22:20:20 | 显示全部楼层
献丑一个简单的玩赖思路:
  1. import random as r

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

评分

参与人数 1荣誉 +3 鱼币 +3 收起 理由
zltzlt + 3 + 3

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
71 
发表于 2020-3-24 04:14:50 | 显示全部楼层
难度评级:中等
要素分析:算法 效率
感受:问题可以转化为对所有数字的符号做规划的二进制问题。
在时间复杂度上面,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))
复制代码

评分

参与人数 1荣誉 +3 鱼币 +3 收起 理由
zltzlt + 3 + 3

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
71 
发表于 2020-3-24 04:48:44 | 显示全部楼层
本帖最后由 阴阳神万物主 于 2020-3-24 04:51 编辑

这个的时间复杂度(算上定义的二进制数据自增函数)应当是 (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))
复制代码

评分

参与人数 1荣誉 +1 鱼币 +1 收起 理由
zltzlt + 1 + 1

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
1 
发表于 2020-3-24 09:28:48 | 显示全部楼层
我飘了 ,我都敢看这样的问题了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
10 
发表于 2020-3-24 09:29:40 | 显示全部楼层
本帖最后由 flamezyy 于 2020-3-24 09:38 编辑
  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])
复制代码

先来个递归的

评分

参与人数 1荣誉 +3 鱼币 +3 收起 理由
zltzlt + 3 + 3

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
1 
发表于 2020-3-24 09:45:38 | 显示全部楼层
  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)
复制代码

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

评分

参与人数 1荣誉 +3 鱼币 +3 收起 理由
zltzlt + 3 + 3

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
1 
发表于 2020-3-24 13:23:16 | 显示全部楼层
看到50鱼币我滚了进来。。。看大佬答题
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1

GMT+8, 2020-9-24 04:33

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表