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

l0stparadise

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

def f358(nums,s):
    if s>sum(nums) or s<-sum(nums):
        return 0
    if (sum(nums)+s)%2:
        return 0
    else:
        real_s=int((sum(nums)+s)/2)
        dp_list=[[0]*(real_s+1) for _ in range(len(nums)) ]
        for _ in range(0,real_s+1):
            if nums[0]==_:
                dp_list[0][_]=1
        for _ in range(0,len(nums)):
            dp_list[_][0]=1
        for i in range(1,len(nums)):
            for k in range(1,real_s+1):
                if nums[i]<=k:
                    dp_list[i][k]=dp_list[i-1][k]+dp_list[i-1][k-nums[i]]
                else:
                    dp_list[i][k] = dp_list[i - 1][k]

        return dp_list[-1][-1]

NAMELESSONE

def solve(nums:list,num:int):
    num = sum(nums)-num
    if num%2 != 0:
        return 0
    target = int(num/2)
    def combinationSum2(candidates, target):
        def dfs(nums, target, start, visited, path, res):
            if target == 0:
                res.append(path + [])
                return 
            for i in range(start, len(nums)):
                if target - nums[i] < 0:
                    return 0
                if i not in visited:
                    visited.add(i)
                    path.append(nums[i])
                    dfs(nums, target - nums[i], i + 1, visited, path, res)
                    path.pop()
                    visited.discard(i)        
        candidates.sort()
        res = []
        visited = set([])
        dfs(candidates, target, 0, visited, [], res)
        return res
    return len(combinationSum2(nums, target))
print(solve([1,3,4,5,1,2,3,4], 3))  

776667

from itertools import permutations

def fun358(nums,s):
    result,n = 0,[]
    symbols = ['+' for i in range(len(nums))] + ['-' for i in range(len(nums))]
    for i in permutations(symbols,len(nums)):
        n.append(i)
    n = list(set(n))
    for i in n:
        formula = ''.join([i[j]+str(nums[j]) for j in range(len(nums))])
        if eval(formula) == s:
            result += 1
    return result

zltzlt

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

108 ms

zltzlt

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

动态规划的解答错误

输入：

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。

from itertools import combinations as cb

def fun358(nums, s):
    # 生成一个等长index列表
    loc = list(range(len(nums)))
    # 初始化计数器变量
    count = 0
    # 全为正值时
    if sum(nums) == s:
        count += 1
    # 全为负数时
    if 0 - sum(nums) == s:
        count += 1
    # 1到n-1个负数时
    for n in range(1, len(nums)):
        # 找出可能的组合
        cb_ls = list(cb(loc, n))
        # 循环这个组合列表，列表的元素是元组
        for x in cb_ls:
            # 复制一个nums的临时列表，用以根据index设置负数
            tmp_nm = nums.copy()
            # 循环这个元组，设置临时列表的相应位置的元素为负数
            for y in x:
                tmp_nm[y] = -1 * tmp_nm[y]
            # 计算和，如果和等于s，那么计数器+1
            if sum(tmp_nm) == s:
                count += 1
    return count

ArmandXiao

def calculate(list_, num, result = 0, tmpList = [], length = 0):
    if not length:
      length = len(list_)  
    list_1 = list_.copy()
    result1 = result
    tmpList_ = tmpList.copy()
    tmpList1 = tmpList.copy()
    if(len(list_)>0):

        result += list_[0]
        tmpList_ += [list_[0]]
        if(result == num and len(tmpList_) == length):
            print(tmpList_, " = ", num)
        list_.pop(0)
        calculate(list_, num, result, tmpList_, length) 

        result1 -= list_1[0]
        tmpList1 += [-list_1[0]]
        if(result1 == num and len(tmpList1) == length):
            print(tmpList1, " = ", num)
        list_1.pop(0)
        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函数的调用，代码如下：

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

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