LeetCode百题【柠檬水找零】

题目描述

解法

贪心
- 我们所持有的面额只有5 10 20
- 相应我们需要找的钱为0 5 15
- 5块钱直接忽略
- 10块钱看还有没有5元的零钱
- 20块钱的分两种情况
  - 5+10
  - 5+5+5
  - 这里优先考虑5+10，因为5元的用处更多，我们要尽可能的保留5元面值的钱

class Solution {
    public boolean lemonadeChange(int[] bills) {
        boolean result = true;
        int money5 = 0;
        int money10 = 0;
        //定义两种面额的持有量，默认为0
        for (int i = 0; i < bills.length; i++) {
            if (bills[i] == 5) {
                money5++;
                //5元直接收
            } else if (bills[i] == 10) {
                if (money5 <= 0) {
                    return false;
                    //找不了直接返回
                } else {
                    money5--;
                    money10++;
                    continue;
                    //三种情况只考虑一直即可直接下次循环
                }
            } else if ((bills[i] == 20)) {
                if (money5 > 0 && money10 > 0) {
                    money5--;
                    money10--;
                    //用5+10的找零
                } else if (money5 > 2) {
                    money5 = money5 - 3;
                    //用3张5元找零
                } else {
                    return false;
                }
            }
        }
        return result;
    }
}