一、題目
LeetCode-860. 檸檬水找零
地址:https://leetcode-cn.com/problems/lemonade-change/
難度:簡(jiǎn)單
在檸檬水?dāng)偵峡恳槐瓩幟仕氖蹆r(jià)為 5 美元拨拓。
顧客排隊(duì)購(gòu)買(mǎi)你的產(chǎn)品酸些,(按賬單 bills 支付的順序)一次購(gòu)買(mǎi)一杯叹话。
每位顧客只買(mǎi)一杯檸檬水凌停,然后向你付 5 美元侮东、10 美元或 20 美元圈盔。你必須給每個(gè)顧客正確找零,也就是說(shuō)凈交易是每位顧客向你支付 5 美元悄雅。
注意驱敲,一開(kāi)始你手頭沒(méi)有任何零錢(qián)。
如果你能給每位顧客正確找零宽闲,返回 true 众眨,否則返回 false 。
示例 1:
輸入:[5,5,5,10,20]
輸出:true
解釋?zhuān)?前 3 位顧客那里容诬,我們按順序收取 3 張 5 美元的鈔票娩梨。
第 4 位顧客那里,我們收取一張 10 美元的鈔票览徒,并返還 5 美元狈定。
第 5 位顧客那里,我們找還一張 10 美元的鈔票和一張 5 美元的鈔票习蓬。
由于所有客戶(hù)都得到了正確的找零纽什,所以我們輸出 true。
示例 2:
輸入:[5,5,10]
輸出:true
示例 3:
輸入:[10,10]
輸出:false
示例 4:
輸入:[5,5,10,10,20]
輸出:false
解釋?zhuān)?前 2 位顧客那里躲叼,我們按順序收取 2 張 5 美元的鈔票芦缰。
對(duì)于接下來(lái)的 2 位顧客,我們收取一張 10 美元的鈔票枫慷,然后返還 5 美元让蕾。
對(duì)于最后一位顧客,我們無(wú)法退回 15 美元或听,因?yàn)槲覀儸F(xiàn)在只有兩張 10 美元的鈔票探孝。
由于不是每位顧客都得到了正確的找零,所以答案是 false神帅。
二再姑、解題思路
本題看起來(lái)很簡(jiǎn)單,直接模擬過(guò)程就行了找御,但為什么是貪心呢元镀?
有三種面值的刀绍填,5,10和20栖疑。
來(lái)顧客時(shí)有如下三種情況:
- 5刀讨永,直接收下。
- 10刀遇革,得找回去一個(gè)5刀卿闹,增加一個(gè)10刀。
- 20刀萝快,優(yōu)先找回去一個(gè)10刀和一個(gè)5刀锻霎,如果10刀不夠,再消耗三個(gè)5刀揪漩。
1和2都是固定策略旋恼,不確定的就有情況3。
貪心策略就在情況3這個(gè)地方奄容,20刀的情況下冰更,為什么要優(yōu)先找回去一個(gè)10刀和一個(gè)5刀呢?(現(xiàn)實(shí)情況中也會(huì)這么做昂勒,多留點(diǎn)零錢(qián)嘛)
10刀只能給20刀找零蜀细,而5刀可以給10刀、20刀找零戈盈。
所以局部最優(yōu)奠衔,遇到20刀,優(yōu)先找零10刀塘娶。盡可能把5刀捏在手里完成更多的找零涣觉,推出全局最優(yōu)。
三血柳、實(shí)現(xiàn)過(guò)程
c++
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
int five = 0,ten = 0;
for(auto& bill:bills){
if(bill == 5){
five++;
}else if(bill == 10){
if(five == 0){
return false;
}
five--;
ten++;
}else{
if(five > 0 && ten > 0){
five--;
ten--;
}else if(five >= 3){
five -= 3;
}else{
return false;
}
}
}
return true;
}
};
PHP
class Solution {
/**
* @param Integer[] $bills
* @return Boolean
*/
function lemonadeChange($bills) {
$five = 0;
$ten = 0;
foreach($bills as $k => $v){
if($v == 5){
$five++;
}else if($v == 10){
if($five == 0){
return false;
}
$five--;
$ten++;
}else{
if($ten > 0 && $five > 0){
$ten--;
$five--;
}else if($five >= 3){
$five -= 3;
}else{
return false;
}
}
}
return true;
}
}
JavaScript
/**
* @param {number[]} bills
* @return {boolean}
*/
var lemonadeChange = function(bills) {
let five = 0,ten = 0;
for(let i = 0;i < bills.length;i++){
if(bills[i] == 5){
five++;
}else if(bills[i] == 10){
if(five == 0){
return false;
}
five--;
ten++;
}else{
if(ten > 0 && five > 0){
ten--;
five--;
}else if(five >= 3){
five -= 3;
}else{
return false;
}
}
}
return true;
};
四、小結(jié)
- 時(shí)間復(fù)雜度:O(n)生兆,其中n是bills的長(zhǎng)度
- 空間復(fù)雜度:O(1)