算法题 柠檬水找零

860. 柠檬水找零

问题描述

在柠檬水摊上，每一杯柠檬水售价5 美元。

顾客排队购买，每位顾客只买一杯，支付的金额可能是5、10 或 20 美元。

你最初没有任何零钱。你需要给每位顾客正确找零，使得净交易是每位顾客向你支付 5 美元。

注意：一开始你没有任何零钱。

返回true如果你能给每位顾客正确找零，否则返回false。

示例：

输入:[5,5,5,10,20]输出:true解释:-前三位顾客支付5美元，无需找零-第四位顾客支付10美元，找零5美元-第五位顾客支付20美元，找零15美元（一张10美元+一张5美元）

输入:[5,5,10,10,20]输出:false解释:-前两位顾客支付5美元-第三位顾客支付10美元，找零5美元-第四位顾客支付10美元，找零5美元-第五位顾客支付20美元，需要找零15美元，但只剩2张5美元（10美元），无法找零

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

算法思路

贪心算法：

1. 核心：

   • 5美元：无需找零，直接收下
   • 10美元：必须找零5美元
   • 20美元：需要找零15美元，有两种方式：
     • 一张10美元 + 一张5美元（优先选择）
     • 三张5美元

2. 贪心策略：

   • 对于20美元的找零，优先使用10美元，保留更多的5美元
   • 5美元的用途更广（可以找零10美元和20美元），而10美元只能用于找零20美元

3. 状态：

   • 只需要记录当前拥有的5美元和10美元的数量
   • 20美元不需要记录，因为无法用于找零

代码实现

方法一：贪心

classSolution{/** * 判断是否能给所有顾客正确找零 * 使用贪心：优先使用10美元找零20美元 * * @param bills 顾客支付的账单数组，每个元素为5、10或20 * @return 如果能正确找零返回true，否则返回false */publicbooleanlemonadeChange(int[]bills){intfive=0;// 5美元的数量intten=0;// 10美元的数量for(intbill:bills){if(bill==5){// 收到5美元，无需找零five++;}elseif(bill==10){// 收到10美元，需要找零5美元if(five>0){five--;ten++;}else{// 没有5美元找零returnfalse;}}else{// bill == 20// 收到20美元，需要找零15美元// 优先使用10+5的组合（贪心策略）if(ten>0&&five>0){ten--;five--;}elseif(five>=3){// 使用5+5+5的组合five-=3;}else{// 无法找零returnfalse;}}}returntrue;}}

算法分析

• 时间复杂度：O(n)
  • n 是顾客数量（bills数组长度）
  • 每位顾客只需要O(1)时间处理
• 空间复杂度：O(1)
  • 只使用了两个整数变量记录零钱数量

算法过程

1：bills = [5,5,5,10,20]

1. 顾客1（5美元）：five=1, ten=0
2. 顾客2（5美元）：five=2, ten=0
3. 顾客3（5美元）：five=3, ten=0
4. 顾客4（10美元）：有5美元，five=2, ten=1
5. 顾客5（20美元）：有10美元和5美元，使用10+5组合，five=1, ten=0
6. 结果：true

2：bills = [5,5,10,10,20]

1. 顾客1（5美元）：five=1, ten=0
2. 顾客2（5美元）：five=2, ten=0
3. 顾客3（10美元）：five=1, ten=1
4. 顾客4（10美元）：five=0, ten=2
5. 顾客5（20美元）：
   • 尝试10+5：有10美元但没有5美元
   • 尝试5+5+5：只有0张5美元 < 3
6. 结果：false

测试用例

publicclassMain{publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：标准成功案例int[]bills1={5,5,5,10,20};System.out.println("Test 1: "+solution.lemonadeChange(bills1));// true// 测试用例2：找零失败int[]bills2={5,5,10,10,20};System.out.println("Test 2: "+solution.lemonadeChange(bills2));// false// 测试用例3：简单成功int[]bills3={5,5,10};System.out.println("Test 3: "+solution.lemonadeChange(bills3));// true// 测试用例4：只有5美元int[]bills4={5,5,5,5,5};System.out.println("Test 4: "+solution.lemonadeChange(bills4));// true// 测试用例5：第一个顾客付10美元int[]bills5={10,10};System.out.println("Test 5: "+solution.lemonadeChange(bills5));// false// 测试用例6：第一个顾客付20美元int[]bills6={20};System.out.println("Test 6: "+solution.lemonadeChange(bills6));// false// 测试用例7：复杂成功案例int[]bills7={5,5,10,20,5,5,5,5,5,5};System.out.println("Test 7: "+solution.lemonadeChange(bills7));// true// 测试用例8：边界情况 - 空数组int[]bills8={};System.out.println("Test 8: "+solution.lemonadeChange(bills8));// true// 测试用例9：单个5美元int[]bills9={5};System.out.println("Test 9: "+solution.lemonadeChange(bills9));// true// 测试用例10：全部20美元int[]bills10={20,20,20};System.out.println("Test 10: "+solution.lemonadeChange(bills10));// false// 测试用例11：贪心策略int[]bills11={5,5,5,5,10,20};System.out.println("Test 11: "+solution.lemonadeChange(bills11));// true// 如果错误地使用5+5+5找零20美元，会导致后续无法找零10美元// 贪心策略会保留5美元// 测试用例12：大量5美元int[]bills12=newint[10000];Arrays.fill(bills12,5);System.out.println("Test 12: "+solution.lemonadeChange(bills12));// true}}

关键点

1. 贪心策略：

   • 5美元比10美元更有价值
   • 优先消耗10美元，保留5美元

2. 状态：

   • 只需要跟踪5美元和10美元的数量
   • 20美元无法用于找零，无需跟踪

3. 边界条件处理：

   • 空数组：返回true（没有顾客需要服务）
   • 第一个顾客付10或20美元：无法找零，返回false

常见问题

1. 为什么不用考虑20美元的数量？
   20美元无法用于找零（只有5、10、20三种面额，20美元太大了），所以收到20美元后直接留在手里，不影响后续找零。

2. 贪心策略是否是最优的？
   5美元的灵活性更高，保留更多5美元永远不会比消耗5美元更差。