37.LeetCode860. 柠檬水找零

• 标签： 贪心
• 难度： 简单

• 题目描述

• 我的解法

用一个散列表 gots 作为记账本，键为钞额， 值为当前收到的张数， 找零的贪心策略是： 尽可能地保留 5 元面额的钞票。比如收到 20 元时， 找零时既可以返还 10 + 5 也可以返还 5 + 5 + 5, 但是我们为了尽可能多地保留 5 元钞， 如果条件允许我们优先返还 10 + 5.

class Solution(object):
    def lemonadeChange(self, bills):
        """
        :type bills: List[int]
        :rtype: bool
        """
        gots = {'5':0, '10':0, '20':0}
        for m in bills:
            if (m==5):
                gots['5'] += 1
                continue
            if(m ==10):
                if(gots['5'] >=1):
                    gots['5'] -= 1
                    gots['10'] += 1
                    continue
                else:
                    return False
            if(m==20):
                if(gots['5'] >=1 and gots['10'] >= 1):
                    gots['5'] -= 1
                    gots['10'] -= 1
                    gots['20'] += 1
                    continue
                if(gots['5'] >= 3):
                    gots['5'] -= 3
                    gots['20'] += 1
                    continue
                return False
        return True
                

• 其他解法

暂略。