leetcode-860-柠檬水找零

题目描述:

在柠檬水摊上,每一杯柠檬水的售价为 5 美元。

顾客排队购买你的产品,(按账单 bills 支付的顺序)一次购买一杯。

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

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

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

示例 1:

输入:[5,5,5,10,20]
输出:true
解释:
前 3 位顾客那里,我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里,我们收取一张 10 美元的钞票,并返还 5 美元。
第 5 位顾客那里,我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零,所以我们输出 true。

示例 2:

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

示例 3:

输入:[10,10]
输出:false

示例 4:

输入:[5,5,10,10,20]
输出:false
解释:
前 2 位顾客那里,我们按顺序收取 2 张 5 美元的钞票。
对于接下来的 2 位顾客,我们收取一张 10 美元的钞票,然后返还 5 美元。
对于最后一位顾客,我们无法退回 15 美元,因为我们现在只有两张 10 美元的钞票。
由于不是每位顾客都得到了正确的找零,所以答案是 false。

提示:

  • 0 <= bills.length <= 10000
  • bills[i] 不是 5 就是 10 或是 20

要完成的函数:

bool lemonadeChange(vector<int>& bills) 

说明:

1. 给定一个vector,里面装着前来购买5元柠檬水的顾客给的钱,只可能会给5元/10元/20元,而你要给他们找零。

初始的时候,你手里面只有柠檬水,而没有任何零钱。如果你能顺利完成所有找零工作(意味着第一个顾客只能给5元,方便你后续找零),那么返回true,如果不能完成所有找零工作,返回false。

2. 这道题也不难,我们定义三个int变量,存储当前5元有多少张,10元有多少张,20元有多少张。

每次有顾客来,判断要找多少零钱,检查一下当前的零钱能不能还,可以就找零,接着下一个顾客。

在找零的过程中,当顾客给了20元,我们优先使用10元和5元的组合找零给顾客,而不是3张5元。

因为5元的零钱更为重要,当顾客使用10元的时候,我们只能找零5元零钱。

如果优先使用3张5元去找零,那么极有可能最终剩下一大堆10元,而当顾客掏出10元购买柠檬水,我们却没有5元零钱来找零。

代码如下:

    bool lemonadeChange(vector<int>& bills) 
    {
        int five=0,ten=0,twenty=0;//定义三个变量,存储每种零钱有几张
        for(int money:bills)
        {
            if(money==5)//如果给了5元,那么不用找零,更新变量就好了
                five++;
            else if(money==10)//如果给了10元,那么判断是否有5元零钱
            {
                if(five>=1)
                    five--;
                else
                    return false;
                ten++;
            }
            else//如果给了20元,先判断是否有10元和5元的组合
            {
                if(ten>=1 && five>=1)
                {
                    ten--;
                    five--;
                }
                else if(five>=3)//如果没有10元和5元的组合,那么使用3张5元
                    five-=3;
                else //如果都没有,那么返回false
                    return false;
                twenty++;
            }
        }
        return true;//顺利完成所有找零工作,返回true
    }

上述代码实测16ms,beats 73.27% of cpp submission。

后记:发现了其实我们也可以不用统计twenty的个数,因为完全不需要用twenty去找零……

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏LinkedBear的个人空间

设计模式笔记(三)——建造者模式 原

将一个复杂对象的构建与它的表示分离,使得同样的构建过程可以创建不同的表示。建造者模式使用多个简单的对象一步一步构建成一个复杂的对象。

662
来自专栏desperate633

LintCode 买卖股票的最佳时机 II题目分析代码

假设有一个数组,它的第i个元素是一个给定的股票在第i天的价格。设计一个算法来找到最大的利润。你可以完成尽可能多的交易(多次买卖股票)。然而,你不能同时参与多个交...

591
来自专栏郭霖

Ruby设计模式透析之 —— 组合(Composite)

Java设计模式透析之 —— 组合(Composite) 听说你们公司最近新推出了一款电子书阅读应用,市场反应很不错,应用里还有图书商城,用户可以在其中随意选...

20710
来自专栏域名资讯

3杂域名22k.com以六位数被售出

随着短域名资源的稀缺,像三杂这类短域名自然成为了抢手货,未来的发展潜力不容小觑,是投资的最佳品种之一。借字符简单、建站不受限制、简洁易记等优势,在米...

2230
来自专栏HansBug's Lab

1935: [Shoi2007]Tree 园丁的烦恼

1935: [Shoi2007]Tree 园丁的烦恼 Time Limit: 15 Sec  Memory Limit: 357 MB Submit: 648 ...

2948
来自专栏数据结构与算法

奖金

【问题描述】   由于无敌的凡凡在2005年世界英俊帅气男总决选中胜出,Yali Company总经理Mr.Z心情好,决定给每位员工发奖金。公司决定以每个人本年...

3638
来自专栏小詹同学

Python系列之六——拿什么拯救你?我的大脑

我一定是智障了,话不多说,上图上图~ ? 就是这样10个选择题,你没有看错,我一定是个智障了~佩服不用穷举,也不用参考网上的大...

3604
来自专栏ACM算法日常

leetcode 题解 | 121. 买卖股票的最佳时机

如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。

1213
来自专栏java工会

猿诗·用java随机生成一首诗

2023
来自专栏C语言及其他语言

[每日一题]发工资咯

题目描述 作为程序猿,最盼望的日子就是每月的9号了,因为这一天是发工资的日子,养家糊口就靠它了,呵呵 但是对于公司财务处的工作人员来说,这一天则是很忙碌的一...

2968

扫码关注云+社区