柠檬水找零
难度:
标签:
题目描述
代码结果
运行时间: 34 ms, 内存: 20.0 MB
/*
* 思路:
* 使用 Java Stream API 和累加器来记录 5 美元和 10 美元的钞票数量,并在每次遇到账单时进行处理。
*/
import java.util.stream.IntStream;
public class LemonadeChangeStream {
public boolean lemonadeChange(int[] bills) {
int[] count = {0, 0}; // count[0] 表示 5 美元的数量, count[1] 表示 10 美元的数量
return IntStream.of(bills).allMatch(bill -> {
switch (bill) {
case 5: count[0]++; return true;
case 10: if (count[0] == 0) return false; count[0]--; count[1]++; return true;
case 20: if (count[1] > 0 && count[0] > 0) { count[1]--; count[0]--; return true; }
else if (count[0] >= 3) { count[0] -= 3; return true; }
else return false;
default: return false;
}
});
}
}
解释
方法:
本题解通过两个计数器,分别记录持有的5美元和10美元的数量。遍历顾客支付的账单数组,根据每位顾客支付的金额,执行相应的找零操作。如果顾客支付5美元,则直接增加5美元计数器。如果支付10美元,检查是否持有5美元来找零,如果有则减少5美元计数器,并增加10美元计数器。如果支付20美元,优先使用一张10美元和一张5美元进行找零,如果不足,尝试使用三张5美元找零。如果在任一步骤中无法提供必要的找零,则返回false。只有全部顾客找零成功后,才返回true。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在处理支付20美元的情况下优先使用一张10美元和一张5美元找零?
▷🦆
如果5美元的计数为0时顾客支付了10美元或20美元,算法是如何处理的?
▷🦆
在算法中,如果无法找到合适的找零方式,直接返回False是否会提前终止整个遍历过程?
▷🦆
在实际应用中,如果bills数组极大,是否有必要对算法进行优化以处理大数据量?
▷