「LeetCode」860-柠檬水找零⚡️

简介: 「LeetCode」860-柠檬水找零⚡️

image.png

前言🌧️


算法,对前端人来说陌生又熟悉,很多时候我们都不会像后端工程师一样重视这项能力。但事实上,算法对每一个程序员来说,都有着不可撼动的地位。


因为开发的过程就是把实际问题转换成计算机可识别的指令,也就是《数据结构》里说的,「设计出数据结构,在施加以算法就行了」。


编写指令的好坏,会直接影响到程序的性能优劣,而指令又由数据结构和算法组成,所以数据结构和算法的设计基本上决定了最终程序的好坏


题目🦀


860. 柠檬水找零


难度简单


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


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

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


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


示例 1:


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


示例 2:


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


提示:


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


解题思路🌵


  • 本题采用贪心算法可以求解
  • 用变量来保存五块和十块的数量
  • 找零钱时尽量先将10块找给顾客


解题步骤🐂


  • 循环遍历每个顾客给的money
  • 优先找零10块,再选择5块的找零
  • 如果是五块的直接记录
  • 如果是10块的,则判断有无五块的数量,没有就返回false
  • 如果是20块的,先判断有一张10块和一张五块的,没有就false
  • 如果没有10块,判断有无3张以上的5块,没有就返回false
  • 遍历完成则返回true


源码🔥



/**
 * @param {number[]} bills
 * @return {boolean}
 */
var lemonadeChange = function(bills) {
    let fiveDollers = 0
    let tenDollers = 0
    for(let i=0;i<bills.length;i++){
        if(bills[i]===5){
            fiveDollers++
        }else if(bills[i]===10){
            if(fiveDollers>0){
                fiveDollers--;
                tenDollers++;
            }else{
                return false
            }
        }else{
            if(tenDollers>0&&fiveDollers>0){
                tenDollers--;
                fiveDollers--;
            }else if(fiveDollers>2){
                fiveDollers-=3;
            }else{
                return false
            }
        }
    }
    return true
};

时间复杂度:O(n)


空间复杂度:O(1)


结束语🌞


image.png

那么鱼鱼的LeetCode算法篇的「LeetCode」860-柠檬水找零⚡️就结束了,算法这个东西没有捷径,只能多写多练,多总结,文章的目的其实很简单,就是督促自己去完成算法练习并总结和输出,菜不菜不重要,但是热爱🔥,喜欢大家能够喜欢我的短文,也希望通过文章认识更多志同道合的朋友,如果你也喜欢折腾,欢迎加我好友,一起沙雕,一起进步

相关文章
|
4月前
代码随想录Day29 贪心04 LeetCode T860 柠檬水找零 T406 根据身高重建队列 T452 用最少得箭引爆气球
代码随想录Day29 贪心04 LeetCode T860 柠檬水找零 T406 根据身高重建队列 T452 用最少得箭引爆气球
25 0
|
6月前
|
算法 Java
代码随想录算法训练营第三十四天 | LeetCode 860. 柠檬水找零、406. 根据身高重建队列、452. 用最少数量的箭引爆气球
代码随想录算法训练营第三十四天 | LeetCode 860. 柠檬水找零、406. 根据身高重建队列、452. 用最少数量的箭引爆气球
39 0
leetcode 860柠檬水找零
leetcode 860柠檬水找零
47 0
leetcode 860柠檬水找零
|
Java
LeetCode 860.柠檬水找零(Java语言)
LeetCode 860.柠檬水找零(Java语言)
64 0
LeetCode 860.柠檬水找零(Java语言)
代码随想录刷题|LeetCode 860.柠檬水找零 406.根据身高重建队列 452. 用最少数量的箭引爆气球
代码随想录刷题|LeetCode 860.柠檬水找零 406.根据身高重建队列 452. 用最少数量的箭引爆气球
代码随想录刷题|LeetCode 860.柠檬水找零 406.根据身高重建队列 452. 用最少数量的箭引爆气球
|
3天前
|
算法 C++
【刷题】Leetcode 1609.奇偶树
这道题是我目前做过最难的题,虽然没有一遍做出来,但是参考大佬的代码,慢慢啃的感觉的真的很好。刷题继续!!!!!!
7 0
|
3天前
|
算法 索引
【刷题】滑动窗口精通 — Leetcode 30. 串联所有单词的子串 | Leetcode 76. 最小覆盖子串
经过这两道题目的书写,相信大家一定深刻认识到了滑动窗口的使用方法!!! 下面请大家继续刷题吧!!!
8 0
|
4天前
|
算法
【刷题】 leetcode 面试题 08.05.递归乘法
递归算法是一种在计算机科学和数学中广泛应用的解决问题的方法,其基本思想是利用问题的自我相似性,即将一个大问题分解为一个或多个相同或相似的小问题来解决。递归算法的核心在于函数(或过程)能够直接或间接地调用自身来求解问题的不同部分,直到达到基本情况(也称为基础案例或终止条件),这时可以直接得出答案而不必再进行递归调用。
21 4
【刷题】 leetcode 面试题 08.05.递归乘法
|
4天前
|
存储 算法 安全
【刷题】 leetcode 面试题 01.06 字符串压缩
来看效果: 非常好!!!过啦!!!
25 5
【刷题】 leetcode 面试题 01.06 字符串压缩