柠檬水找零

本文主要是介绍柠檬水找零，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

柠檬水找零

题⽬描述

在柠檬⽔摊上，每⼀杯柠檬⽔的售价为 5 美元。顾客排队购买你的产品，（按账单 bills ⽀付

的顺序）⼀次购买⼀杯。

每位顾客只买⼀杯柠檬⽔，然后向你付 5 美元、 10 美元或 20 美元。你必须给每个顾客正确找

零，也就是说净交易是每位顾客向你⽀付 5 美元。

注意，⼀开始你⼿头没有任何零钱。

给你⼀个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确

找零，返回 true ，否则返回 false 。

 示例：

⽰例 1：

输⼊：bills = [5,5,5,10,20]

输出：true

解释：

前 3 位顾客那⾥，我们按顺序收取 3 张 5 美元的钞票。

第 4 位顾客那⾥，我们收取⼀张 10 美元的钞票，并返还 5 美元。

第 5 位顾客那⾥，我们找还⼀张 10 美元的钞票和⼀张 5 美元的钞票。

由于所有客⼾都得到了正确的找零，所以我们输出 true。

⽰例 2：

输⼊：bills = [5,5,10,10,20]

输出：false

解释：

前 2 位顾客那⾥，我们按顺序收取 2 张 5 美元的钞票。

对于接下来的 2 位顾客，我们收取⼀张 10 美元的钞票，然后返还 5 美元。

对于最后⼀位顾客，我们⽆法退回 15 美元，因为我们现在只有两张 10 美元的钞票。

由于不是每位顾客都得到了正确的找零，所以答案是 false。

提⽰：

◦ 1 <= bills.length <= 10(5)

◦ bills[i] 不是 5 就是 10 或是 20

解法（贪⼼）：

 public static boolean lemonadeChange(int[] bills) {int five =0;int ten =0;for (int i = 0; i < bills.length; i++) {if (bills[i]==5){five++;}else if (bills[i]==10){if (five>=1){five--;ten++;}else {return false;}}else {if (ten>=1 && five>=1){ten--;five--;}else if (five>=3&&ten==0){five-=3;}else {return false;}}}return true;}

 证明

贪⼼策略：

证明

采用交换论证法：

这题的最优解和贪心解的区别是——采用先1个5块和1个10块来，找零20块.

交换论证法：

在不破坏最优解的情况下，可以把最优解调整成贪心解.

当我们手上有1个10块和3个5块的时候，先用3个5块，中的2个5块完全可以用10块代替。

这样就可以在不破坏最优解的情况下，可以把最优解调整成贪心解了.

这篇关于柠檬水找零的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---