【每日一题Day273】LC860柠檬水找零 | 贪心

简介: 【每日一题Day273】LC860柠檬水找零 | 贪心

柠檬水找零【LC860】

在柠檬水摊上,每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品,(按账单 bills 支付的顺序)一次购买一杯。

每位顾客只买一杯柠檬水,然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零,也就是说净交易是每位顾客向你支付 5 美元。

注意,一开始你手头没有任何零钱。

给你一个整数数组 bills ,其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零,返回 true ,否则返回 false 。

来源:力扣(LeetCode

链接:https://leetcode.cn/problems/lemonade-change

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

  • 贪心
    遇到20美元时优先使用10美元找零
  • 实现
class Solution {
    public boolean lemonadeChange(int[] bills) {
        int num5 = 0;
        int num10 = 0;
        for (int i = 0; i < bills.length; i++){
            if (bills[i] == 5){
                num5++;
            }else if (bills[i] == 10){
                if (num5 > 0){
                    num5--;
                    num10++;
                }else{
                    return false;
                }
            }else{
                if (num10 > 0 && num5 > 0){
                    num10--;
                    num5--;
                }else if (num5 >= 3){
                    num5 -= 3;
                }else{
                    return false;
                }
            }
        }
        return true;
    }
}
class Solution {
    public 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) {
                five--;
                ten++;
            } else if (bills[i] == 20) {
                if (ten > 0) {
                    ten--;
                    five--;
                } else {
                    five -= 3;
                }
            }
            if (five < 0 || ten < 0) return false;
        }
        return true;
    }
}

image.png

目录
相关文章
|
6月前
【每日一题Day334】LC2591将钱分给最多的儿童 | 贪心
【每日一题Day334】LC2591将钱分给最多的儿童 | 贪心
47 0
|
6月前
|
算法
【每日一题Day363】LC275H 指数Ⅱ | 二分答案
【每日一题Day363】LC275H 指数Ⅱ | 二分答案
55 0
|
1月前
lanqiao oj 186 糖果(状态压缩dp)
lanqiao oj 186 糖果(状态压缩dp)
13 0
|
3月前
|
算法
【算法】贪心算法——柠檬水找零
【算法】贪心算法——柠檬水找零
|
6月前
|
算法
【贪心算法】|860.柠檬水找零
【贪心算法】|860.柠檬水找零
|
6月前
|
存储
每日一题啦(● ̄(エ) ̄●)(尼克切斯定理,等差数列)
每日一题啦(● ̄(エ) ̄●)(尼克切斯定理,等差数列)
30 0
|
6月前
代码随想录 Day38 完全背包问题 LeetCode T70 爬楼梯 T322 零钱兑换 T279 完全平方数
代码随想录 Day38 完全背包问题 LeetCode T70 爬楼梯 T322 零钱兑换 T279 完全平方数
37 0
|
6月前
蓝桥备战--分糖果OJ2928 贪心 分类讨论
蓝桥备战--分糖果OJ2928 贪心 分类讨论
67 0
|
6月前
|
Java
leetcode-860:柠檬水找零
leetcode-860:柠檬水找零
57 0
|
6月前
【每日一题Day330】LC337打家劫舍Ⅲ | 动态规划
【每日一题Day330】LC337打家劫舍Ⅲ | 动态规划
35 0