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

fan1993423

1. def fun328(lst):
   
2.     bill_dict={5:0,10:0}
   
3.     for i in lst:
   
4.         if i==5:
   
5.             bill_dict[i]+=1
   
6.         elif i==10:
   
7.             bill_dict[i]+=1
   
8.             bill_dict[5]-=1
   
9.             if bill_dict[5]<0:
   
10.                 return False
    
11.         else:
    
12.             bill_dict[10]-=1
    
13.             bill_dict[5]-=1
    
14.             if bill_dict[10]<0 or bill_dict[5]<0:
    
15.                 bill_dict[10]+=1
    
16.                 bill_dict[5]-=2
    
17.                 if bill_dict[5]<0:return False
    
18.     return True

复制代码

无脑解的，因为只有5,10,20这几种面值，如果面值多了，应该不能无脑解

fan1993423

比方说有5,10,15,20,25,30,35...100这种，难度陡然上升

jdzzj

1. def fun328(bills):
   
2. 
   
3.     count1 = 0  # 用于计算5元可供找零的次数
   
4.     count2 = 0  # 用于计算10元可供找零的次数
   
5. 
   
6.     for i in bills:
   
7.         if i == 5:
   
8.             count1 += 1
   
9.         if i == 10:
   
10.             if count1 < 1:
    
11.                 return False
    
12.             count1 -= 1
    
13.             count2 += 1
    
14.         if i == 20:
    
15.             if count2 > 0 and count1 > 0:  # 如果有10元和5元的，先用10元和5元的找零
    
16.                 count2 -= 1
    
17.                 count1 -= 1
    
18.             elif count2 == 0 and count1 > 0:  # 没有10元的,只能用5元的找零
    
19.                 if count1 < 3:
    
20.                     return False
    
21.                 count1 -= 3
    
22.             else:
    
23.                 return False
    
24.     return True

复制代码

zltzlt

William4869 发表于 2020-2-9 22:41
无脑解法，，反正情况很少

196 ms

zltzlt

TJBEST 发表于 2020-2-9 22:58
算了，今日事今日毕吧 我刚看错题了 以为 钱有很多种了 原来才3钟钱啊 如果 超过 三种 就得递归了

168 ms

zltzlt

阴阳神万物主 发表于 2020-2-9 23:14
按照楼主的描述，好像不涉及有其他商贩可以进行零钱交易的渠道，那么我就苦恼了，比较纠结。
比如：这种情 ...

zltzlt

546623863 发表于 2020-2-9 23:48
话说这玩意有其他解法吗

164 ms

zltzlt

yexing 发表于 2020-2-10 00:40
试了试用列表来储存数据，写的时候思路不是很清晰，可能存在未发现的 bug ：

解答错误

输入：[5, 5, 5, 5, 20, 20, 5, 5, 20, 5]
输出：True
预期结果：False

超萌哒水狗君

1. # coding=gbk
   
2. have = []
   
3. def zhaoqian(t): # 需要找t元
   
4.     if t == 0:
   
5.         return True
   
6.     low_have = [i for i in have if i <= t] # 把不大于t的筛选出来
   
7.     low_have.sort(reverse=True)
   
8.     for i in low_have:
   
9.         have.remove(i)
   
10.         if not zhaoqian(t-i):
    
11.             have.append(i)
    
12.         else:
    
13.             return True
    
14.     return False
    
15. def fun(bill):
    
16.     for i in bill:
    
17.         if i == 5:
    
18.             have.append(5)
    
19.         elif i % 5 != 0: # 不是5的整数倍一定不可以！
    
20.             return False
    
21.         else:
    
22.             have.append(i) # 把钱收下
    
23.             if not zhaoqian(i-5): # 开始暴力求解
    
24.                 return False
    
25.     return True

复制代码

相当暴力的解法

wanting-for

1. def solve_326(bills:list):
   
2.     i = 0
   
3.     x = 0
   
4.     y = len(bills)
   
5.     while True:
   
6.         if x == y:
   
7.             return True
   
8.         if bills[i] - 5 == 0:
   
9.             i += 1
   
10.             x += 1
    
11.             continue
    
12.         else:
    
13.             x += 1
    
14.             each, num = bills[i] - 5, 0
    
15.             ls = bills[:i]
    
16.             ls.sort()
    
17.             for j in range(len(ls)-1, -1, -1):
    
18.                 if ls[j] <= each:
    
19.                     each -= ls[j]
    
20.                     bills.remove(ls[j])
    
21.                     num += 1
    
22.                     if each == 0:
    
23.                         break
    
24.             if each != 0:
    
25.                 return False
    
26.             else:
    
27.                 i -= (num-1)
    
28. print(solve_326([5, 5, 5, 5, 20, 20, 5, 5, 20, 5]))
    

复制代码

写的太复杂了。。。

zltzlt

kinkon 发表于 2020-2-10 03:53

160 ms

zltzlt

776667 发表于 2020-2-10 11:32

224 ms

zltzlt

fan1993423 发表于 2020-2-10 12:49
无脑解的，因为只有5,10,20这几种面值，如果面值多了，应该不能无脑解

64 ms

zltzlt

jdzzj 发表于 2020-2-10 12:51

204 ms

fan1993423

zltzlt 发表于 2020-2-11 18:48
64 ms

我是不是最快的？另327题麻烦在测一下吧。我把走不通的设置成0了，现在改了

zltzlt

fan1993423 发表于 2020-2-11 19:03
我是不是最快的？另327题麻烦在测一下吧。我把走不通的设置成0了，现在改了

收到

echolihappy

mark