贪婪问题,每一次找钱都要让自己手中留下尽可能多的5r
// 这题很简单,不涉及算法,按正常逻辑写就行,Runtime: 1 ms, faster than 100.00%
class Solution {
public boolean lemonadeChange(int[] bills) {
if (bills[0] != 5) return false;
int five = 0, ten = 0; // 保存可找的钱
for (int i : bills) {
if (i == 5) five++; // 不用找钱,只收钱
else if (five < 1) return false; // 只要找钱,一定会用到5r
else {
five--; // 不论后面怎么找钱都要给最少一张5r,提取出来简化代码
if (i == 10) ten++;
else if (ten >= 1) ten--;
else if (five >= 2) five -= 2;
else return false;
}
}
return true;
}
}
// 更简短但是时间效率低一些的写法,Runtime: 2 ms, faster than 62.08%
class Solution {
public boolean lemonadeChange(int[] bills) {
if (bills[0] != 5) return false;
int five = 0, ten = 0; // 保存可找的钱
for (int i : bills) {
if (i == 5) five++;
else if (i == 10) {five--; ten++;}
else if (i == 20 && ten > 0) {five--; ten--;}
else five -=3;
if (five < 0) return false; // 最后再检查five,小于0就是不够找,return false
}
return true;
}
}