鱼C论坛

 找回密码
 立即注册
查看: 1306|回复: 34

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

[复制链接]
发表于 2020-1-24 21:21:15 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
今天的题目:


给定若干不同面额的硬币(coins)和总金额(amount),计算可以凑成总金额的硬币组合数。

说明:每一种面额的硬币均有无限个。

示例 1:

输入:amount = 5, coins = [1, 2, 5]
输出:4
解释:有四种方式可以凑成总金额:
5 = 5
5 = 2 + 2 + 1
5 = 2 + 1 + 1 + 1
5 = 1 + 1 + 1 + 1 + 1
示例 2:

输入:amount = 3, coins = [2]
输出:0
解释:只用面额 2 的硬币不能凑成总金额 3。
示例 3:

输入:amount = 10, coins = [10]
输出:1


欢迎大家一起答题!
最佳答案
2020-1-25 15:38:28
zltzlt 发表于 2020-1-25 15:32
解答错误

输入:amount = 100, coins = [99, 1]

我去,sort弄掉了
  1. def func314(amount:int,coins:list)->int:
  2.     if len(coins)==0:
  3.         if amount==0:
  4.             return 1
  5.         else:
  6.             return 0
  7.     coins.sort()        
  8.     l=[[1]*len(coins)]
  9.     for i in range(1,amount+1):
  10.         a,t=0,[]
  11.         for j in range(len(coins)):
  12.             if coins[j]>i:
  13.                 t.extend([a]*(len(coins)-j))
  14.                 break
  15.             a+=l[i-coins[j]][j]
  16.             t.append(a)
  17.         l.append(t)
  18.     return l[-1][-1]
复制代码

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2020-1-24 21:56:36 From FishC Mobile | 显示全部楼层
春节快乐,呃,明天再想。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-1-25 10:25:46 | 显示全部楼层
本帖最后由 塔利班 于 2020-1-25 10:32 编辑
  1. def f314(amount,coins):
  2.     res=0
  3.     c=len(coins)
  4.     #coins.sort()  好像没用,如果性能不行加上试试看
  5.     def dp(a,c):
  6.         nonlocal res
  7.         if not a:
  8.             res+=1
  9.         elif not c:
  10.             return
  11.         else:
  12.             b=c[-1]
  13.             for i in range(0,a+1,b):
  14.                 dp(a-i,c[:-1])
  15.     dp(amount,coins)
  16.     return res
复制代码

先写个

评分

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

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-1-25 11:00:20 | 显示全部楼层

输入 amount = 500,coins = [3, 5, 7, 8, 9, 10, 11] 超时,加上 sort 也一样。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-1-25 11:09:51 | 显示全部楼层
春节快乐!先不解题
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-1-25 11:11:07 | 显示全部楼层

新年快乐!

既然来了就想想呗
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-1-25 13:01:54 | 显示全部楼层
为什么这题我有印象?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-1-25 15:18:33 | 显示全部楼层
总感觉还能优化
  1. def func314(amount:int,coins:list)->int:
  2.     if len(coins)==0:
  3.         return 0
  4.     coins.sort()
  5.     l=[[1]*len(coins)]
  6.     for i in range(1,amount+1):
  7.         a,t=0,[]
  8.         for j in range(len(coins)):
  9.             if coins[j]>i:
  10.                 t.extend([a]*(len(coins)-j))
  11.                 break
  12.             a+=l[i-coins[j]][j]
  13.             t.append(a)
  14.         l.append(t)
  15.     return l[-1][-1]
复制代码

评分

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

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-1-25 15:24:28 | 显示全部楼层
Croper 发表于 2020-1-25 15:18
总感觉还能优化

解答错误

输入:amount = 0, coins = []
输出:0
预期结果:1
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-1-25 15:27:07 | 显示全部楼层
zltzlt 发表于 2020-1-25 15:24
解答错误

输入:amount = 0, coins = []

这用例够刁钻~
  1. def func314(amount:int,coins:list)->int:
  2.     if len(coins)==0:
  3.         if amount==0:
  4.             return 1
  5.         else:
  6.             return 0
  7.     l=[[1]*len(coins)]
  8.     for i in range(1,amount+1):
  9.         a,t=0,[]
  10.         for j in range(len(coins)):
  11.             if coins[j]>i:
  12.                 t.extend([a]*(len(coins)-j))
  13.                 break
  14.             a+=l[i-coins[j]][j]
  15.             t.append(a)
  16.         l.append(t)
  17.     return l[-1][-1]
复制代码

评分

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

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-1-25 15:32:51 | 显示全部楼层

解答错误

输入:amount = 100, coins = [99, 1]
输出:1
预期结果:2
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-1-25 15:38:28 From FishC Mobile | 显示全部楼层    本楼为最佳答案   
zltzlt 发表于 2020-1-25 15:32
解答错误

输入:amount = 100, coins = [99, 1]

我去,sort弄掉了
  1. def func314(amount:int,coins:list)->int:
  2.     if len(coins)==0:
  3.         if amount==0:
  4.             return 1
  5.         else:
  6.             return 0
  7.     coins.sort()        
  8.     l=[[1]*len(coins)]
  9.     for i in range(1,amount+1):
  10.         a,t=0,[]
  11.         for j in range(len(coins)):
  12.             if coins[j]>i:
  13.                 t.extend([a]*(len(coins)-j))
  14.                 break
  15.             a+=l[i-coins[j]][j]
  16.             t.append(a)
  17.         l.append(t)
  18.     return l[-1][-1]
复制代码

评分

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

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-1-25 15:39:15 | 显示全部楼层
Croper 发表于 2020-1-25 15:38
我去,sort弄掉了

336 ms
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-1-25 18:00:43 | 显示全部楼层
输入:amount = 0, coins = [1,2,3,4]
输出结果是什么呢?是1还是0
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-1-25 18:10:56 | 显示全部楼层
TJBEST 发表于 2020-1-25 18:00
输入:amount = 0, coins = [1,2,3,4]
输出结果是什么呢?是1还是0

1
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-1-25 18:37:20 | 显示全部楼层
新年快乐!这个程序是初步的,我试了一下准确但是超时,我再想想办法改改,思路上得变化
  1. def fun314(amount,coins):
  2.     def inner(amount,position):
  3.         temp = MaxToMin[position]
  4.         if position < M - 1:
  5.             if amount > temp:
  6.                 div = amount // temp
  7.                 for i in range(0,div):
  8.                     inner(amount-i*temp,position + 1)
  9.                 if amount % temp == 0:
  10.                     res[0]=res[0] + 1
  11.                 else:
  12.                     inner(amount-div*temp,position + 1)
  13.             elif amount == temp:
  14.                 res[0] = res[0] + 1
  15.                 inner(amount,position + 1)
  16.             else:
  17.                 inner(amount,position + 1)
  18.         else:
  19.             if amount % temp == 0:
  20.                 res[0]=res[0] + 1
  21.             else:
  22.                 pass
  23.             
  24.     if coins == []:
  25.         if amount == 0:
  26.             return 1
  27.         else:
  28.             return 0
  29.     else:
  30.         pass
  31.   
  32.     if amount == 0:
  33.         return 1
  34.     else:
  35.         pass

  36.     MaxToMin = sorted(coins)
  37.     MaxToMin.reverse()
  38.     M = len(MaxToMin)
  39.     res = [0]
  40.     inner(amount,0)
  41.     return res[0]
复制代码

评分

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

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-1-25 19:04:11 | 显示全部楼层
TJBEST 发表于 2020-1-25 18:37
新年快乐!这个程序是初步的,我试了一下准确但是超时,我再想想办法改改,思路上得变化

输入 amount = 500,coins = [3, 5, 7, 8, 9, 10, 11] 超时。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-1-25 20:25:55 | 显示全部楼层
zltzlt 发表于 2020-1-25 11:11
新年快乐!

既然来了就想想呗

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-1-25 22:09:03 | 显示全部楼层
  1. def solve(list1:list,all,list_sum=[],list3=[]):
  2.     list1.sort()
  3.     list1.reverse()
  4.     count = 0
  5.     if all == 0:
  6.         return 1
  7.     for i in range(len(list1)):
  8.         list_sum.append(list1[i])
  9.         if sum(list_sum) == all:
  10.             count+=1
  11.         elif sum(list_sum)<all:
  12.             list3 = list1[i:]
  13.             #list_sum.append(i)
  14.             count+=solve(list3,all,list_sum)
  15.         m = list_sum.pop()
  16.     return count
  17. print(solve([3,2,1],6))  
复制代码

输入这个amount = 500,coins = [3, 5, 7, 8, 9, 10, 11],指定超时,而且调用堆栈也太多次,内存也会超。
不知道对于小数据是否准确

评分

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

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-1-25 22:11:36 | 显示全部楼层
wanting-for 发表于 2020-1-25 22:09
输入这个amount = 500,coins = [3, 5, 7, 8, 9, 10, 11],指定超时,而且调用堆栈也太多次,内存也会超 ...

输入 amount = 500,coins = [1, 2, 5] 就会超时
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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

GMT+8, 2024-3-29 16:05

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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