題目
在檸檬水攤上,每一杯檸檬水的售價為 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。
解題思路
對所有顧客付的錢bills做遍歷,分三種情況,bill為5元,10元和20元。bill為5元時,肯定能找零,直接返回true;bill為10元時,需要確定有沒有保留5元,否則返回false;bill為20元時,需要確定有沒有保留10元和5元,優先消耗10元的,如果沒有,則返回false。
代碼實現
class Solution {
public:bool lemonadeChange(vector<int>& bills) {int five = 0, ten = 0;for (int bill : bills) {// 情況一if (bill == 5) five++;// 情況二if (bill == 10) {if (five <= 0) return false;ten++;five--;}// 情況三if (bill == 20) {// 優先消耗10美元,因為5美元的找零用處更大,能多留著就多留著if (five > 0 && ten > 0) {five--;ten--;} else if (five >= 3) {five -= 3;} else return false;}}return true;}
};