鱼C论坛

 找回密码
 立即注册
楼主: zltzlt

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

[复制链接]
最佳答案
0 
发表于 2020-3-24 14:01:28 | 显示全部楼层
本帖最后由 l0stparadise 于 2020-3-24 14:22 编辑

动态规划学习中,感觉好难
  1. def f358(nums,s):
  2.     if s>sum(nums) or s<-sum(nums):
  3.         return 0
  4.     if (sum(nums)+s)%2:
  5.         return 0
  6.     else:
  7.         real_s=int((sum(nums)+s)/2)
  8.         dp_list=[[0]*(real_s+1) for _ in range(len(nums)) ]
  9.         for _ in range(0,real_s+1):
  10.             if nums[0]==_:
  11.                 dp_list[0][_]=1
  12.         for _ in range(0,len(nums)):
  13.             dp_list[_][0]=1
  14.         for i in range(1,len(nums)):
  15.             for k in range(1,real_s+1):
  16.                 if nums[i]<=k:
  17.                     dp_list[i][k]=dp_list[i-1][k]+dp_list[i-1][k-nums[i]]
  18.                 else:
  19.                     dp_list[i][k] = dp_list[i - 1][k]

  20.         return dp_list[-1][-1]
复制代码

评分

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

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
1 
发表于 2020-3-24 15:41:57 | 显示全部楼层
  1. def solve(nums:list,num:int):
  2.     num = sum(nums)-num
  3.     if num%2 != 0:
  4.         return 0
  5.     target = int(num/2)
  6.     def combinationSum2(candidates, target):
  7.         def dfs(nums, target, start, visited, path, res):
  8.             if target == 0:
  9.                 res.append(path + [])
  10.                 return
  11.             for i in range(start, len(nums)):
  12.                 if target - nums[i] < 0:
  13.                     return 0
  14.                 if i not in visited:
  15.                     visited.add(i)
  16.                     path.append(nums[i])
  17.                     dfs(nums, target - nums[i], i + 1, visited, path, res)
  18.                     path.pop()
  19.                     visited.discard(i)        
  20.         candidates.sort()
  21.         res = []
  22.         visited = set([])
  23.         dfs(candidates, target, 0, visited, [], res)
  24.         return res
  25.     return len(combinationSum2(nums, target))
  26. print(solve([1,3,4,5,1,2,3,4], 3))  
复制代码

评分

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

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
3 
发表于 2020-3-24 17:25:26 | 显示全部楼层
本帖最后由 776667 于 2020-3-24 17:31 编辑
  1. from itertools import permutations

  2. def fun358(nums,s):
  3.     result,n = 0,[]
  4.     symbols = ['+' for i in range(len(nums))] + ['-' for i in range(len(nums))]
  5.     for i in permutations(symbols,len(nums)):
  6.         n.append(i)
  7.     n = list(set(n))
  8.     for i in n:
  9.         formula = ''.join([i[j]+str(nums[j]) for j in range(len(nums))])
  10.         if eval(formula) == s:
  11.             result += 1
  12.     return result
复制代码

评分

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

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
2851 
 楼主| 发表于 2020-3-24 17:53:25 | 显示全部楼层
kinkon 发表于 2020-3-23 19:01
貌似要用到动态规则或者递归

108 ms
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
2851 
 楼主| 发表于 2020-3-24 17:55:46 | 显示全部楼层

动态规划的解答错误

输入:
  1. nums = [1, 0], s = 1
复制代码

输出:1
预期结果:2

第一个超时
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
2851 
 楼主| 发表于 2020-3-24 17:56:20 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
2851 
 楼主| 发表于 2020-3-24 17:56:40 | 显示全部楼层

好久没发悬赏题了……
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
2851 
 楼主| 发表于 2020-3-24 17:57:15 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
1802 
发表于 2020-3-24 18:10:31 | 显示全部楼层
zltzlt 发表于 2020-3-24 17:55
动态规划的解答错误

输入:

已改
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 2020-3-24 18:11:04 | 显示全部楼层

大佬  麻烦解释一下第二段代码是啥意思
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
2 
发表于 2020-3-24 18:22:56 | 显示全部楼层
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)

评分

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

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
1802 
发表于 2020-3-24 18:30:38 | 显示全部楼层
1556134029 发表于 2020-3-24 18:11
大佬  麻烦解释一下第二段代码是啥意思

如果是长度1的Nums就检查这个数添加正负号是否=s
如果大于1,就吧第一个数单拿出来,把他和s组合到一起,然后剩下的Nums继续,如此递归直到满足长度1截止
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
2 
发表于 2020-3-24 19:25:30 | 显示全部楼层
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

评分

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

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
127 
发表于 2020-3-24 19:59:25 | 显示全部楼层
本帖最后由 suchocolate 于 2020-3-24 20:05 编辑

我的思路:
1)全是+号算一下:
2)全是-号算一下:
3)其他情况用排列组合出置-1 index列表,分别算出sum。
  1. from itertools import combinations as cb

  2. def fun358(nums, s):
  3.     # 生成一个等长index列表
  4.     loc = list(range(len(nums)))
  5.     # 初始化计数器变量
  6.     count = 0
  7.     # 全为正值时
  8.     if sum(nums) == s:
  9.         count += 1
  10.     # 全为负数时
  11.     if 0 - sum(nums) == s:
  12.         count += 1
  13.     # 1到n-1个负数时
  14.     for n in range(1, len(nums)):
  15.         # 找出可能的组合
  16.         cb_ls = list(cb(loc, n))
  17.         # 循环这个组合列表,列表的元素是元组
  18.         for x in cb_ls:
  19.             # 复制一个nums的临时列表,用以根据index设置负数
  20.             tmp_nm = nums.copy()
  21.             # 循环这个元组,设置临时列表的相应位置的元素为负数
  22.             for y in x:
  23.                 tmp_nm[y] = -1 * tmp_nm[y]
  24.             # 计算和,如果和等于s,那么计数器+1
  25.             if sum(tmp_nm) == s:
  26.                 count += 1
  27.     return count
复制代码

评分

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

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
4 
发表于 2020-3-24 20:35:33 | 显示全部楼层
  1. def calculate(list_, num, result = 0, tmpList = [], length = 0):
  2.     if not length:
  3.       length = len(list_)  
  4.     list_1 = list_.copy()
  5.     result1 = result
  6.     tmpList_ = tmpList.copy()
  7.     tmpList1 = tmpList.copy()
  8.     if(len(list_)>0):

  9.         result += list_[0]
  10.         tmpList_ += [list_[0]]
  11.         if(result == num and len(tmpList_) == length):
  12.             print(tmpList_, " = ", num)
  13.         list_.pop(0)
  14.         calculate(list_, num, result, tmpList_, length)

  15.         result1 -= list_1[0]
  16.         tmpList1 += [-list_1[0]]
  17.         if(result1 == num and len(tmpList1) == length):
  18.             print(tmpList1, " = ", num)
  19.         list_1.pop(0)
  20.         calculate(list_1, num, result1, tmpList1, length)
复制代码

评分

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

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 2020-3-25 16:59:17 | 显示全部楼层
kinkon 发表于 2020-3-23 19:01
貌似要用到动态规则或者递归

大神太强了可以麻烦解析一下这个算法吗
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
2851 
 楼主| 发表于 2020-3-25 17:35:10 | 显示全部楼层
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 超时
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
2851 
 楼主| 发表于 2020-3-25 17:35:49 | 显示全部楼层

解答错误

输入:nums = [1], s = 1
输出:0
预期结果:1
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
2851 
 楼主| 发表于 2020-3-25 17:36:53 | 显示全部楼层
ouyunfu 发表于 2020-3-23 21:02
挑战一行代码
如果是python3.8版本,可以使用海象运算符“:=”,减少一次len函数的调用,代码如下:

第二段代码有错哦
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
2851 
 楼主| 发表于 2020-3-25 17:37:53 | 显示全部楼层
ouyunfu 发表于 2020-3-23 21:02
挑战一行代码
如果是python3.8版本,可以使用海象运算符“:=”,减少一次len函数的调用,代码如下:

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

  1. nums = [0, 0, 0, 0, 0, 0, 0, 0, 1], s = 1
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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

GMT+8, 2020-10-25 18:30

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

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