思路:
收到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
结果无误,但是速度太慢,反复对元素进行添加,查找,删除等操作。
其实根本没必要对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
复杂度分析:
- 时间复杂度:O(n),遍历bills
- 空间复杂度O(1).