专栏首页前端小书童【一天一大 lee】柠檬水找零 (难度:简单) - Day20201210

【一天一大 lee】柠檬水找零 (难度:简单) - Day20201210

20201210

题目:

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

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

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

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

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

示例:

  1. 示例 1:
输入:[5,5,5,10,20]
输出:true
解释:
前 3 位顾客那里,我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里,我们收取一张 10 美元的钞票,并返还 5 美元。
第 5 位顾客那里,我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零,所以我们输出 true。
  1. 示例 2:
输入:[5,5,10]
输出:true
  1. 示例 3:
输入:[10,10]
输出:false
  1. 示例 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

抛砖引玉

抛砖引玉

思路

不能正确找零分两种:

  1. 手里的零钱不够找
  2. 手里的零钱找不开,因为零钱只有 5、10、20 三种所有找不开的情况时手中一定没有 5、15

那么每次交易时需要知道 手里的钱数还需要知道手里是否能组合出 5、15

当遇到需要找零 15 时,优先使用 10+5 组合。

  • num:手中零钱的总数
  • numF:手中 5 元的数量
  • numT:手中 10 元的数量
/**
 * @param {number[]} bills
 * @return {boolean}
 */
var lemonadeChange = function(bills) {
    let index = 0,
        num = 0,
        numF = 0,
        numT = 0,
        len = bills.length
    while (index < len) {
        // 需要的找零
        const item = bills[index] - 5
        if (num < item) return false
        if (item === 5) {
            // 没有5元
            if (!numF) return false
            numF--
            numT++
        } else if (item === 15) {
            if (numF && numT) {
                numF--
                numT--
            } else if (numF >= 3) {
                numF -= 3
            } else {
                // 无法组合出15
                return false
            }
        } else {
            numF++
        }
        num += 5
        index++
    }
    return true
}

博客: 前端小书童

每天的每日一题,写的题解会同步更新到公众号一天一大 lee 栏目 欢迎关注留言

公众号:前端小书童

本文分享自微信公众号 - 前端小书童(gaowenju_web),作者:前端小书童

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-12-10

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【一天一大 lee】柠檬水找零 (难度:简单) - Day20201211

    Dota2 参议院由来自两派的参议员组成。现在参议院希望对一个 Dota2 游戏里的改变作出决定。他们以一个基于轮为过程的投票进行。在每一轮中,每一位参议员都可...

    前端小书童
  • 【观点】从大数据看美国的“柠檬危机”

    柠檬价格连创新高,令美国人高呼“柠檬危机”来了,但通过大数据分析历年柠檬的价格表明,柠檬定价受季节性因素影响较大,春季历来是价格高点,但随着产量...

    小莹莹
  • 【一天一大 lee】移动零 (难度:简单) - Day20201119

    给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

    前端小书童
  • 【一天一大 lee】找不同 (难度:简单) - Day20201218

    字符串 t 由字符串 s 随机重排,则说明字符的位置已经不能作为查找的依据了,只能从字符数量入手去看:

    前端小书童
  • 免费增长业务模式如何成为 SaaS 强大的增长策略

    ? 来源|作者:李宽wideplum  ---- 今天编译一篇生动有趣的文章,通俗易懂的来讲一讲SaaS的免费模式。 ? 夏天到了!阳光,假期,海滩...

    腾讯SaaS加速器
  • Python高能小技巧:用海象操作符减少重复代码

    导读:赋值表达式(assignment expression)是Python 3.8新引入的语法,它会用到海象操作符(walrus operator)。这种写法...

    华章科技
  • 拧灯泡,煲鸡汤,抓豆腐!韩国这款“工业实用型软体抓手”厉害了!

    红枣炖鸡汤,此汤可补脾益气补血。食材:三黄鸡1只,红枣数个,葱末少许,盐。方法:1. 鸡冼净切大块,放进开水里过开水去浮末,2. 加入红枣……哎,我是不是走错了...

    大数据文摘
  • 机器学习中对抗性攻击的介绍和示例

    对抗样本是专门设计的输入,旨在欺骗机器学习 (ML) 模型,从而导致高置信度的错误分类。有趣的是这种方式对图像所做的修改虽然温和,但足以欺骗 ML 模型。在这篇...

    deephub
  • 【一天一大 lee】查找常用字符 (难度:简单) - Day20201014

    给定仅有小写字母组成的字符串数组 A,返回列表中的每个字符串中都显示的全部字符(包括重复字符)组成的列表。例如,如果一个字符在每个字符串中出现 3 次,但不是 ...

    前端小书童
  • 一天一大 lee(单词搜索)难度:简单-Day20200913

    单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

    前端小书童
  • 【一天一大 lee】单词规律 (难度:简单) - Day20201216

    给定一种规律 pattern 和一个字符串 str ,判断 str 是否遵循相同的规律。

    前端小书童
  • 快速拿下面试算法

    在面试前一周,我刷了很多道算法,分类刷,有些是做过的,因为我是面试C++相关岗位,除了leetcode与剑指offer相关的算法,还需要手撕一些智能指针呀,单例...

    公众号guangcity
  • 腾讯课堂全面升级联合投放策略 助力机构流量精准投放与规模化获取

    ? 在互联网流量红利消失的时代背景下,在线职业教育机构面临流量获取难、付费转化率低、获客成本高等重重困难和挑战。同时,受疫情影响,线下教育机构纷纷转型线上,行...

    鹅老师
  • 力扣(LeetCode)刷题,简单题(第22期)

    力扣(LeetCode)定期刷题,每期10道题,业务繁重的同志可以看看我分享的思路,不是最高效解决方案,只求互相提升。

    不脱发的程序猿
  • 一天一大 lee(图像渲染)难度:简单-Day20200816

    有一幅以二维整数数组表示的图画,每一个整数表示该图画的像素值大小,数值在 0 到 65535 之间。

    前端小书童
  • 一天一大 lee(相同的树)难度:简单-Day20200807

    前端小书童
  • 【一天一大 lee】长按键入 (难度:简单) - Day20201021

    你的朋友正在使用键盘输入他的名字 name。偶尔,在键入字符 c 时,按键可能会被长按,而字符可能被输入 1 次或多次。

    前端小书童
  • 【一天一大 lee】回文链表 (难度:简单) - Day20201023

    前端小书童
  • 【一天一大 lee】杨辉三角 (难度:简单) - Day20201206

    杨辉三角:是二项式系数在三角形中的一种几何排列。它是中国古代数学的杰出研究成果之一,它把二项式系数图形化,把组合数内在的一些代数性质直观地从图形中体现出来,是一...

    前端小书童

扫码关注云+社区

领取腾讯云代金券