[LeetCode] 860. 柠檬水找零 lemonade-change(贪心算法）

思路：

收到5块时，只是添加；收到十块时，添加10块，删除一个5块；收到20块时，添加20，删除一个10块一个5块，或者直接删除3个5块(注意:这里先删除5+10优于3个5)

class Solution(object):def lemonadeChange(self, bills):""":type bills: List[int]:rtype: bool"""exchange=[]for i in bills:exchange.append(i)if i==5:continueelif i==10:if exchange.count(5)>=1:exchange.remove(5)else:return Falseelse:if exchange.count(5)>=1 and exchange.count(10)>=1:exchange.remove(5)exchange.remove(10)elif exchange.count(5)>=3:exchange.remove(5)exchange.remove(5)exchange.remove(5)else:return Falsereturn True

结果无误，但是速度太慢，反复对元素进行添加，查找，删除等操作。

其实根本没必要对bills的元素反复进行查找删除操作，只需要2个整数分别记录5块，10块的个数即可。

class Solution(object):def lemonadeChange(self, bills):""":type bills: List[int]:rtype: bool"""five,ten=0,0for i in bills:if i==5:five+=1elif i==10:ten+=1if five>=1:five-=1else:return Falseelse:if five>=1 and ten>=1:five-=1ten-=1elif five>=3:five-=3else:return Falsereturn True

复杂度分析：

时间复杂度：O(n)，遍历bills空间复杂度O(1).

如果觉得《[LeetCode] 860. 柠檬水找零 lemonade-change(贪心算法）》对你有帮助，请点赞、收藏，并留下你的观点哦！