IOS 算法(基础篇) ----- 柠檬水找零

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。
顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
注意，一开始你手头没有任何零钱。
如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

例子

输入：[5,5,5,10,20]
输出：true

输入：[5,5,10]
输出：true

输入：[5,5,10,10,20]
输出：false

循环法(栈)

最容易理解的方法
实现我们定义两个"储钱罐", 一个存放5元, 一个存放10元, 循环判断处理

1.5元进罐
2.10元, 5元1个出罐, 5元不够false, 10元进罐
3.20元, 10元1个出罐5元1个出罐, 或者 3个5元出罐(没有10元情况下), 5元不够false

    func lemonadeChange(_ bills: [Int]) -> Bool {
        
        var arr5:[Int] = [], arr10:[Int] = []
        for num in bills {
            if num == 5 {

                arr5.append(num)

            }else if num == 10 {

                if arr5.count == 0 {
                    return false
                }
                arr5.removeLast()
                arr10.append(num)

            }else if num == 20 {

                if arr5.count == 0 || (arr10.count == 0 && arr5.count < 3) {
                    return false
                }
                arr5.removeLast()

                if arr10.count != 0 {
                    arr10.removeLast()
                }else{
                    arr5.removeLast()
                    arr5.removeLast()
                }
            }
        }
        return true
    }

方法2 贪心算法

其实我认为贪心算法处理这道题比较好, 解释直接写代码里面了

    func lemonadeChange(_ bills: [Int]) -> Bool {
        //定义两个"计数器", 1个记5, 1个记10
        var five = 0, ten = 0
        //循环
        for i in 0..<bills.count {
            if bills[i] == 5 {
                //如果是5 5的计数器 + 1
                five += 1
                
            } else if bills[i] == 10 {
                //如果是10 10的计数器 + 1, 5的计数器 - 1
                five -= 1
                ten += 1
                
            } else if ten > 0 {
                //能走到这里, 说明 bills[i] = 20
                //我们直接判断 10的计数器是否 > 0
                //10的计数器 > 0 说明可以找1张10元, 1张5元
                //10的计数器 - 1, 5的计数器 - 1
                ten -= 1
                five -= 1
                
            } else { 
                //10的计数器 < 0, 说明要3张5元
                //5的计数器 - 3
                five -= 3
            }
            //最后判断, 5的计数器是否小于0, 小于说明不能满足账单需求
            if five < 0 {

                return false
            }
        }

        return true
    }

题目来源：力扣（LeetCode） 感谢力扣爸爸 :)
IOS 算法合集地址