[已解决]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

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 = [0] * (result + 1)
    sa[0] = 1
    for i in nums:
        for j in range(result, i - 1, -1):
            sa[j] += sa[j - i]
    return sa[result]

跳转到最佳答案楼层

蒋博文

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 = [0] * (result + 1)
    sa[0] = 1
    for i in nums:
        for j in range(result, i - 1, -1):
            sa[j] += sa[j - i]
    return sa[result]

kinkon

能不能多一些例子？

kinkon

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

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 = [1]+[0]*b
    for i in nums:
        for j in range(b, i-1, -1):
            m[j] += m[j-i]

    return m[b]

塔利班

暴力

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[0]+str(a[1]) 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[0]+b,b-a[0]).count(0)
        else:
            return dp(a[1:],a[0]+b)+dp(a[1:],b-a[0])
    return dp(nums,s)

March2615

# (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 = [0] * (S + 1)
    dp[0] = 1
    for num in nums:
        for j in range(S, num-1, -1):
            dp[j] += dp[j-num]
    return dp[S]


if __name__ == '__main__':
    nums = [1, 2, 3, 4]
    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], i + 1) + dfs(cur - nums[i], i + 1)
        return d.get((i, cur), int(cur == s))
    return dfs(0, 0)

TJBEST

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

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

def fun358(nums,s):
    def inner(end,num):
        if end==1:
            if num != 0:
                if nums[0]==num or nums[0]==-num:
                    return 1
                else:
                    return 0
            else:
                if nums[0]==0:
                    return 2
                else:
                    return 0
        else:
            return inner(end-1,num - nums[end-1])+inner(end-1,num + nums[end-1])
    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[0]==num or nums[0]==-num:
                    dic[(1,num)]=1
                    return 1
                else:
                    dic[(1,num)]=0
                    return 0
            else:
                if nums[0]==0:
                    dic[(1,num)]=2
                    return 2
                else:
                    dic[(1,num)]=0
                    return 0
        else:
            temp = inner(end-1,num - nums[end-1])+inner(end-1,num + nums[end-1])
            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[0]:
                return 0
            elif n == list1[0]:
                return 1
            else:
                if f(list1[1:],n-list1[0]):
                    return count+f(list1[1:],n-list1[0])
        x = 0
        while nums != [] and add >= nums[0]:
            x += f(nums,add)
            nums = nums[1:]
        return x

ouyunfu

挑战一行代码

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

流浪的杰

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

fan1993423

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[0]==s or nums[0]==-s:
            return count0
        else:
            return 0
    nums.reverse()
    result=0
    def recursion(nums,s):
        nonlocal result,count0
        if len(nums)==1:
            if nums[0]==s or nums[0]==-s:
                result+=1
                return result
            else:
                return result
        s+=nums[0]
        if sum(nums[1:])>s:
            recursion(nums[1:],s)+recursion(nums[1:],s-nums[0]*2)
        elif sum(nums[1:])==s:
            result+=1
            return recursion(nums[1:],s-nums[0]*2)
        else:
            return recursion(nums[1:],s-nums[0]*2)
        return result
    return recursion(nums,s)*count0

sjtuszy

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

import random as r

def fun358(nums, s):
    a = len(nums)
    x = [1 for i in range(a)]
    m = n = 0
    
    while m < 10000:
        for each in range(a):
            x[each] = r.choice([-1, 1])
        if sum((nums[i]*x[i]) 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[j] if l[j] else -nums[j]
        if su < s:continue
        while (j := j+1)<r:
            su -= nums[j]
        if su == s:
            res += 1
    return res
if __name__ == '__main__':
    print('示例 输出：',solve([1]*5,3))

阴阳神万物主

这个的时间复杂度（算上定义的二进制数据自增函数）应当是 (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[i]:self[i] = 0
                    else:self[i] += 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[i] if l[i] else -nums[i]
        if su < s:continue
        while (i := i+1)<r:
            su -= nums[i]
        if su == s:
            print(l)
            res += 1
    return res
if __name__ == '__main__':
    print('示例 输出：',solve_2([1]*5,3))

AINIDEREN

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

flamezyy

def f358(nums, s):
    if sum(nums) < abs(s):
        return 0
    elif len(nums) == 2:
        if nums[0] + nums[1] == abs(s):
            return 1
        elif abs(nums[0] - nums[1]) == abs(s):
            if s == 0:
                return 2
            else:
                return 1
    else:
        return f358(nums[:-1], s-nums[-1]) + f358(nums[:-1], s+nums[-1])

先来个递归的

mdphd

x = [1, 1, 1, 1, 1]
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)[2:].zfill(n)
    b = 0
    for j in range(n):
        b += fh(a[j], x[j])
    if b == s:
        ct += 1
print(ct)

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

xiaomei47580

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