一起學(xué)算法-860. 檸檬水找零

一、題目

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í)有如下三種情況:

  1. 5刀讨永,直接收下。
  2. 10刀遇革,得找回去一個(gè)5刀卿闹,增加一個(gè)10刀。
  3. 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é)

  1. 時(shí)間復(fù)雜度:O(n)生兆,其中n是bills的長(zhǎng)度
  2. 空間復(fù)雜度:O(1)
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末难捌,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子鸦难,更是在濱河造成了極大的恐慌根吁,老刑警劉巖,帶你破解...
    沈念sama閱讀 218,640評(píng)論 6 507
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件合蔽,死亡現(xiàn)場(chǎng)離奇詭異击敌,居然都是意外死亡,警方通過(guò)查閱死者的電腦和手機(jī)拴事,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 93,254評(píng)論 3 395
  • 文/潘曉璐 我一進(jìn)店門(mén)沃斤,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)圣蝎,“玉大人,你說(shuō)我怎么就攤上這事衡瓶∨枪” “怎么了?”我有些...
    開(kāi)封第一講書(shū)人閱讀 165,011評(píng)論 0 355
  • 文/不壞的土叔 我叫張陵哮针,是天一觀的道長(zhǎng)关面。 經(jīng)常有香客問(wèn)我,道長(zhǎng)十厢,這世上最難降的妖魔是什么等太? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 58,755評(píng)論 1 294
  • 正文 為了忘掉前任,我火速辦了婚禮蛮放,結(jié)果婚禮上缩抡,老公的妹妹穿的比我還像新娘。我一直安慰自己筛武,他們只是感情好缝其,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,774評(píng)論 6 392
  • 文/花漫 我一把揭開(kāi)白布。 她就那樣靜靜地躺著徘六,像睡著了一般内边。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上待锈,一...
    開(kāi)封第一講書(shū)人閱讀 51,610評(píng)論 1 305
  • 那天漠其,我揣著相機(jī)與錄音,去河邊找鬼竿音。 笑死和屎,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的春瞬。 我是一名探鬼主播柴信,決...
    沈念sama閱讀 40,352評(píng)論 3 418
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼宽气!你這毒婦竟也來(lái)了随常?” 一聲冷哼從身側(cè)響起,我...
    開(kāi)封第一講書(shū)人閱讀 39,257評(píng)論 0 276
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤萄涯,失蹤者是張志新(化名)和其女友劉穎绪氛,沒(méi)想到半個(gè)月后,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體涝影,經(jīng)...
    沈念sama閱讀 45,717評(píng)論 1 315
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡枣察,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,894評(píng)論 3 336
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片序目。...
    茶點(diǎn)故事閱讀 40,021評(píng)論 1 350
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡臂痕,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出宛琅,到底是詐尸還是另有隱情刻蟹,我是刑警寧澤,帶...
    沈念sama閱讀 35,735評(píng)論 5 346
  • 正文 年R本政府宣布嘿辟,位于F島的核電站舆瘪,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏红伦。R本人自食惡果不足惜英古,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,354評(píng)論 3 330
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望昙读。 院中可真熱鬧召调,春花似錦、人聲如沸蛮浑。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 31,936評(píng)論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)沮稚。三九已至艺沼,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間蕴掏,已是汗流浹背障般。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 33,054評(píng)論 1 270
  • 我被黑心中介騙來(lái)泰國(guó)打工, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留盛杰,地道東北人挽荡。 一個(gè)月前我還...
    沈念sama閱讀 48,224評(píng)論 3 371
  • 正文 我出身青樓,卻偏偏與公主長(zhǎng)得像即供,于是被迫代替她去往敵國(guó)和親定拟。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,974評(píng)論 2 355

推薦閱讀更多精彩內(nèi)容