贪心算法|柠檬水找零_【贪心算法(二)】柠檬水找零

题目描述

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

解题分析

加入顾客给的是五元则无需找零，给十元时只能用五元找零，给二十元时有5*3和10+5两种找零方式，所以每收到一次钱的时候要首先判断其数值，然后再判断手里已有的五元和十元的数量，二十元的不涉及找零，所以不用考虑其数量，最终返回结果。

代码

public boolean lemonadeChange(int[] bills) {
		int five = 0, ten = 0;
		for (int bill : bills) {
			if (bill == 5) {
				five++;
			} else if (bill == 10) {
				if (five == 0) {
					return false;
				}
				five--;
				ten++;
			} else {
				if (five > 0 && ten > 0) {
					five--;
					ten--;
				} else if (five >= 3) {
					five -= 3;
				} else {
					return false;
				}
			}
		}
		return true;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

参考视频链接：https://b23.tv/kQNmu5