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

解答错误

输入：

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

复制代码

输出：8
预期结果：256

zltzlt

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

解答错误

输入：

1. 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  ...

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

1. def fun358(nums,s):
   
2.     M = len(nums)
   
3.     dic = dict()
   
4.     if nums[0] == 0:
   
5.         dic[0] = 2
   
6.     else:
   
7.         temp = nums[0]
   
8.         dic[temp] = 1
   
9.         dic[-temp] = 1
   
10.     for each in range(1,M):
    
11.         dic_temp = dict()
    
12.         temp = nums[each]
    
13.         for eachEle in dic:
    
14.             if nums[each] == 0:
    
15.                 try:
    
16.                     dic_temp[eachEle] = dic_temp[eachEle] + 2 * dic[eachEle]
    
17.                 except Exception:
    
18.                     dic_temp[eachEle] = 2 * dic[eachEle]
    
19.             else:
    
20.                 try:
    
21.                     dic_temp[eachEle + temp] = dic_temp[eachEle + temp] + dic[eachEle]
    
22.                 except Exception:
    
23.                     dic_temp[eachEle + temp] = dic[eachEle]
    
24.                 try:
    
25.                     dic_temp[eachEle - temp] = dic_temp[eachEle - temp] + dic[eachEle]
    
26.                 except Exception:
    
27.                     dic_temp[eachEle - temp] = dic[eachEle]
    
28.         dic = dic_temp
    
29.     return dic[s]

复制代码

蒋博文

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

lawsonwang

直接用背包试试。

1. def T358(nums, s):
   
2.     if sum(nums)<s or (s+sum(nums))%2: # 不可能成功，剪枝
   
3.         return 0
   
4.     n=int((s+sum(nums))/2)
   
5.     dp=[1]+[0]*n
   
6.     # 似乎是动态规划？背包？
   
7.     for i in nums:
   
8.         for j in range(n, i-1, -1): # 动态规划
   
9.             dp[j]=dp[j]+dp[j-i]
   
10. 
    
11.     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

输入以下数据超时：

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

复制代码