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

分析:如果第一份账单不为5元,则肯定不能找零,返回false。之后的账单若为10元,则判断是否有5元的,若没有,则也不能找零,返回false,否则,5元的剩余数fiveCount自减,10元的余额数自增。若账单为20元,则找零有这两种情况,即5,5,5或10,5.

若两种情况都可采用,优先选择10,5找零(因为5元既可以找10元的订单,又可以找20元的订单,尽量保留)。若这两种情况都不存在,则不能找零,返回false。当最后账单执行完,则成功全部找零,返回true。

代码实现:

# include<stdio.h>

 int lemonadeChange(int* bills,int length) {
    if (bills[0] != 5){  //第一份账单不为5,无法找零
        return 0; //返回0,表示为fasle,假
    }
    else{
        int fiveCount = 1, tenCount = 0; //初始化计数变量
        for (int i = 1; i<length; i++){
            if (bills[i] == 5){  //账单为5元的情况
                fiveCount++;
            }
            else if (bills[i] == 10){ //账单为10元的情况
                if (fiveCount == 0){
                    return 0;
                }
                else{
                    fiveCount--;
                    tenCount++;
                }
            }
            else{     //账单为20的情况
                if (fiveCount == 0){
                    return 0;
                }
                else if (tenCount != 0){
                    fiveCount--;
                    tenCount--;
                }
                else{
                    if (fiveCount >= 3){
                        fiveCount -= 3;
                    }
                    else{
                        return 0;
                    }
                }
            }
        }
        return 1; //返回1,表示为true,真
    }
}

int main (){ //此处为一个测试例子
    int bill[] = { 5, 5, 10, 10, 20 };
    printf("%d\n", lemonadeChange(bill,5));
}

原文发布于微信公众号 - ACM算法日常(acm-clan)

原文发表时间:2018-11-11

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏JetpropelledSnake

Python实现简单的三级菜单

话不多说,直奔代码 # 要处理的字典 dic1 = { '北京': { '东城': { ...

6449
来自专栏chenjx85的技术专栏

leetcode-860-柠檬水找零

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

BZOJ1569: [JSOI2008]Blue Mary的职员分配(dp 暴力)

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

奖金

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

3648
来自专栏老九学堂

数制系统讲解

什么是数制系统?数制就是人类创造的数的表示方法,使用一系列数码符号和一套统一的规则来表示数据,大多数人都熟悉罗马数制系统I、II、III、IV、V、VI、VII...

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

P1796 汤姆斯的天堂梦_NOI导刊2010提高(05)

题目描述 汤姆斯生活在一个等级为0的星球上。那里的环境极其恶劣,每天12小时的工作和成堆的垃圾让人忍无可忍。他向往着等级为N的星球上天堂般的生活。 有一些航班将...

2768
来自专栏小詹同学

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

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

3654
来自专栏大数据钻研

JavaScript 世界万物诞生记

一. 无中生有 起初,什么都没有。 造物主说:没有东西本身也是一种东西啊,于是就有了null: ? 现在我们要造点儿东西出来。但是没有原料怎么办? 有一个声音说...

3388
来自专栏desperate633

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

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

591
来自专栏落影的专栏

程序员进阶之算法练习(十一)有感而发

前言 经过这几年的观察,我发现,国内本科高校的ACM集训队,往往汇聚着该校相对靠谱的那一批人。 拿本校举例,队内的众学长学姐毕业之后,有去国内top2的高校...

37310

扫码关注云+社区

领取腾讯云代金券