carloscn
commented
1 year ago 问题分析
该程序的逻辑分为以下几种情况：
- 当收入的数值是5的时候，直接入队
- 当收入的数值是10的时候，消耗一个5的元素
- 当收入的数值是20的时候（贪心）：
- 如果有10元，优先消耗一个10元，再消耗一个5元
- 如果没有10元，消耗三个5元。
拆分功能，我们需要能够快速查找自己当前存有多少5元，多少10元，多少20元。我们准备三个池子，分别装这些零钱，然后再去根据业务逻辑push和pop。
fn is_change(array:Vec<i32>) -> bool
{
let mut five_pool:Vec<i32> = vec![];
let mut ten_pool:Vec<i32> = vec![];
for e in &array {
match *e {
5 => {
five_pool.push(*e);
},
10 => {
if five_pool.is_empty() {
return false;
}
five_pool.pop();
ten_pool.push(*e);
},
20 => {
if !ten_pool.is_empty() {
if five_pool.is_empty() {
return false;
}
ten_pool.pop();
five_pool.pop();
} else {
if five_pool.len() < 3 {
return false;
}
for i in [0..2] {
five_pool.pop();
}
}
},
_ => {
return false;
}
}
}
return true;
}
问题描述
注意，一开始你手头没有任何零钱。
给你一个整数数组 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 <= 105 bills[i] 不是 5 就是 10 或是 20
来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/lemonade-change