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

思路:

收到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:
continue
elif i==10:
if exchange.count(5)>=1:
exchange.remove(5)
else:
return False
else:
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 False
return True

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

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

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

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

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

复杂度分析:

  • 时间复杂度:O(n),遍历bills
  • 空间复杂度O(1).
05-11 13:39