前言🌧️
算法,对前端人来说陌生又熟悉,很多时候我们都不会像后端工程师一样重视这项能力。但事实上,算法对每一个程序员来说,都有着不可撼动的地位。
因为开发的过程就是把实际问题转换成计算机可识别的指令,也就是《数据结构》里说的,「设计出数据结构,在施加以算法就行了」。
编写指令的好坏,会直接影响到程序的性能优劣,而指令又由数据结构和算法组成,所以数据结构和算法的设计基本上决定了最终程序的好坏。
题目🦀
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)
结束语🌞
那么鱼鱼的LeetCode算法篇的「LeetCode」860-柠檬水找零⚡️
就结束了,算法这个东西没有捷径,只能多写多练,多总结,文章的目的其实很简单,就是督促自己去完成算法练习并总结和输出,菜不菜不重要,但是热爱🔥,喜欢大家能够喜欢我的短文,也希望通过文章认识更多志同道合的朋友,如果你也喜欢折腾
,欢迎加我好友
,一起沙雕
,一起进步
。