题目来源:860. 柠檬水找零
解法:贪心由于每一杯柠檬水的售价为5美元,顾客只可能给你5美元、10美元和20美元三个面值的钞票,并且,一开始你手头没有任何零钱。据此,我们可以进行如下的分类讨论:
- 顾客给5美元,直接收下5美元
- 顾客给10美元,收下10美元,找零5美元
- 顾客给20美元,收下20美元,此时有2种找零方法:
- 有10美元和5美元,则找零1张10美元和1张5美元
- 只有5美元,则找零3张5美元
因为5美元的使用场景比10美元的使用场景广,所以当顾客给20美元时,我们优先采用第一种找零方法,尽量保留手里的5美元。(贪心)
综上所述,我们定义five记录5美元的数量,ten记录10美元的数量,初始化均为0。遍历bills数组,对每一个bill采用上述找零策略,失败则return false,全部完成则return true。
代码:bool lemonadeChange(int* bills, int billsSize){ int five=0,ten=0; for(int i=0;i复杂度分析0) { ten++; five--; } else return false; } else { if(ten>0 && five>0) { ten--; five--; } else if(five>=3) five-=3; else return false; } } return true; }
时间复杂度:O(N),其中N是bills的长度。
空间复杂度:O(1)。
结果:欢迎分享,转载请注明来源:内存溢出
评论列表(0条)