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

小甲鱼de粉丝

永恒的蓝色梦想 发表于 2020-3-23 20:37
悬赏50，nb

一般的吧，我还有见过200

小甲鱼de粉丝

xiaomei47580 发表于 2020-3-24 13:23
看到50鱼币我滚了进来。。。看大佬答题

哈哈 哈

zltzlt

fan1993423 发表于 2020-3-23 21:49

解答错误

输入：

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

输出：8
预期结果：256

zltzlt

sjtuszy 发表于 2020-3-23 22:20
献丑一个简单的玩赖思路：

解答错误

输入：

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

输出：268
预期结果：256

fan1993423

@zltzlt 12楼已改

kinkon

小马爱python 发表于 2020-3-25 16:59
大神太强了可以麻烦解析一下这个算法吗

一同学习，我也是初学者，只是做的题比较多

月明

写C不香吗

TJBEST

zltzlt 发表于 2020-3-25 17:35
输入 nums = [31, 4, 45, 3, 44, 49, 28, 6, 22, 24, 40, 25, 13, 46, 17, 10, 2, 38, 25, 15], s = 25  ...

楼主 我又写了一个，应该可以了，不是递归

def fun358(nums,s):
    M = len(nums)
    dic = dict()
    if nums[0] == 0:
        dic[0] = 2
    else:
        temp = nums[0]
        dic[temp] = 1
        dic[-temp] = 1
    for each in range(1,M):
        dic_temp = dict()
        temp = nums[each]
        for eachEle in dic:
            if nums[each] == 0:
                try:
                    dic_temp[eachEle] = dic_temp[eachEle] + 2 * dic[eachEle]
                except Exception:
                    dic_temp[eachEle] = 2 * dic[eachEle]
            else:
                try:
                    dic_temp[eachEle + temp] = dic_temp[eachEle + temp] + dic[eachEle]
                except Exception:
                    dic_temp[eachEle + temp] = dic[eachEle]
                try:
                    dic_temp[eachEle - temp] = dic_temp[eachEle - temp] + dic[eachEle]
                except Exception:
                    dic_temp[eachEle - temp] = dic[eachEle]
        dic = dic_temp
    return dic[s]

蒋博文

楼主，能不能测试一下16楼，谢谢。

lawsonwang

直接用背包试试。

def T358(nums, s):
    if sum(nums)<s or (s+sum(nums))%2: # 不可能成功，剪枝
        return 0
    n=int((s+sum(nums))/2)
    dp=[1]+[0]*n
    # 似乎是动态规划？背包？
    for i in nums:
        for j in range(n, i-1, -1): # 动态规划
            dp[j]=dp[j]+dp[j-i]

    return dp[n]

lawsonwang

我恨不得用C或C++，都用惯了C++，转成Python费了点功夫

zltzlt

ouyunfu 发表于 2020-3-23 21:02
挑战一行代码
如果是python3.8版本，可以使用海象运算符“:=”,减少一次len函数的调用，代码如下：

第二段代码有语法错误哦

zltzlt

阴阳神万物主 发表于 2020-3-24 04:14
难度评级：中等
要素分析：算法 效率
感受：问题可以转化为对所有数字的符号做规划的二进制问题。

输入 nums = [42, 24, 30, 14, 38, 27, 12, 29, 43, 42, 5, 18, 0, 1, 12, 44, 45, 50, 21, 47], s = 38 超时

zltzlt

阴阳神万物主 发表于 2020-3-24 04:48
这个的时间复杂度（算上定义的二进制数据自增函数）应当是 (2**n)*n

输入 nums = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], s = 1 超时

zltzlt

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

84 ms

zltzlt

flamezyy 发表于 2020-3-24 09:29
先来个递归的

输入 nums = [1], s = 1 出错

zltzlt

mdphd 发表于 2020-3-24 09:45
暴力破解
尝试优化算法遇阻，只能暴力

输入 nums = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], s = 0 超时

zltzlt

l0stparadise 发表于 2020-3-24 14:01
动态规划学习中，感觉好难

解答错误

输入：nums = [0, 0, 0, 0, 0, 0, 0, 0, 1], s = 1
输出：1
预期结果：256

zltzlt

NAMELESSONE 发表于 2020-3-24 15:41

解答错误

输入：nums = [1, 0], s =  1
输出：1
预期结果：2

zltzlt

776667 发表于 2020-3-24 17:25

输入以下数据超时：

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