LeetCode 柠檬水找零问题

Record my own stupidity. 20200514

• 自己的沙雕写法：

class Solution:
   def lemonadeChange(self, bills: List[int]) -> bool:
       # 当前的钱都是整数倍的 因此可以使用贪心算法
       cur = [] # 随时维护的数组
       for bill in bills:
           if bill == 5:
               cur.append(bill)
           if bill == 10:
               if cur.count(5) > 0:
                   idx = cur.index(5)
                   cur.pop(idx)
                   cur.append(10)
               else:
                   return False
           if bill == 20:
               # 找零15
               # 10+5
               if cur.count(10)>0 and cur.count(5)>0:
                   idxs_10 = cur.index(10)
                   cur.pop(idxs_10)
                   idxs_5 = cur.index(5)
                   cur.pop(idxs_5)
                   cur.append(20)
                   
               elif cur.count(5) >= 3:
                   for i in range(3):
                       idxs_5 = cur.index(5)
                       cur.pop(idxs_5)
                   cur.append(20)
               else:
                   return False
       return True

因为用到了list.index()方法，导致增加了很多遍历列表的操作。

• 大佬题解

class Solution(object): 
    def lemonadeChange(self, bills):
        five = ten = 0
        for bill in bills:
            if bill == 5:
                five += 1
            elif bill == 10:
                if not five: return False
                five -= 1
                ten += 1
            else:
                if ten and five:
                    ten -= 1
                    five -= 1
                elif five >= 3:
                    five -= 3
                else:
                    return False
        return True

只记录零钱的数量，不需要用列表维护。

菜的痛心疾首