朋友們、伙計(jì)們，我們又見面了，本專欄是關(guān)于各種算法的解析，如果看完之后對你有一定的啟發(fā)，那么請留下你的三連，祝大家心想事成！

C 語 言 專 欄：C語言：從入門到精通

數(shù)據(jù)結(jié)構(gòu)專欄：數(shù)據(jù)結(jié)構(gòu)

個(gè)? 人? 主? 頁?：stackY、

C + + 專 欄? ?：C++

Linux 專?欄? ：Linux

目錄

1. 題目解析

2. 算法原理講解

3. 代碼實(shí)現(xiàn)

4. 貪心策略證明

1. 題目解析

LeetCode860.檸檬水找零：https://leetcode.cn/problems/lemonade-change/description/https://leetcode.cn/problems/lemonade-change/description/

860. 檸檬水找零

在檸檬水?dāng)偵?，每一杯檸檬水的售價(jià)為?5?美元。顧客排隊(duì)購買你的產(chǎn)品，（按賬單?bills?支付的順序）一次購買一杯。

每位顧客只買一杯檸檬水，然后向你付?5?美元、10?美元或?20?美元。你必須給每個(gè)顧客正確找零，也就是說凈交易是每位顧客向你支付?5?美元。

注意，一開始你手頭沒有任何零錢。

給你一個(gè)整數(shù)數(shù)組?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 美元，因?yàn)槲覀儸F(xiàn)在只有兩張 10 美元的鈔票。
由于不是每位顧客都得到了正確的找零，所以答案是 false。

提示：

• 1 <= bills.length <= 105
• bills[i]?不是?5?就是?10?或是?20?

根據(jù)題意：首先找零是按照順序來進(jìn)行的，不能“插隊(duì)”，并且剛開始我們身無分文。

假設(shè)第一個(gè)顧客給5塊，那么直接收下即可；

如果第一個(gè)顧客給的不是5塊，那表示需要給顧客找零，但是此時(shí)我們沒有錢，所以直接返回false即可。?

2. 算法原理講解

首先：我們根據(jù)顧客支付的錢可以分為三種情況：

1. 顧客支付5元 -> 直接收下即可；

2. 顧客支付10元 -> 直接收下，并且判斷身上是否有5元，如果有找零給顧客，如果沒有直接返回false；

3. 顧客支付20元 -> 直接收下，此時(shí)給顧客找零就存在兩種方法：

????????① 找給顧客一張10元和一張5元；

? ? ? ? ② 找給顧客三張5元；

那么該如何選擇上述兩種情況呢？

就需要用到貪心算法，那么到底該怎么貪才是最優(yōu)呢？

上面的兩種方法其本質(zhì)上就是一張10元與兩張5元的區(qū)別，那么根據(jù)貪心策略該怎么貪呢？

仔細(xì)觀察不難發(fā)現(xiàn)，5元的用處是很大的，不僅可以給10元找零，還可以給20元找零，那么既然5元用處這么大，就表示5元比較珍貴，所以越珍貴的東西我們越舍不得用，所以盡量選擇找零5元比較少的那一個(gè)方法，所以我們的貪心策略是：盡可能少的使用5元錢給顧客找零。

3. 代碼實(shí)現(xiàn)

怎么記錄我們手上的錢呢？

可以使用兩個(gè)變量來統(tǒng)計(jì)此時(shí)我們手中所具有的5元錢的張數(shù)（cnt_five）和10元錢cnt_ten），然后遍歷bills，遇到5元將cnt_five++，遇到10元錢先看自己手里有沒有錢，遇到20元首先考慮的就是10+5的策略，再考慮5+5+5的策略。

class Solution 
{
public:
    bool lemonadeChange(vector<int>& bills) 
    {
        //統(tǒng)計(jì)5元錢和10元錢的張數(shù)
        int cnt_ten = 0, cnt_five = 0; 
        //遍歷
        for(auto& e : bills)
        {
            if(e == 5) cnt_five++;   //遇到5元就收下
            else if(e == 10)         //遇到10元
            {
                cnt_ten++;
                if(cnt_five) cnt_five--; //先判斷是否可以找零
                else return false;
            }
            else                     //遇到20元
            {
                if(cnt_five && cnt_ten) //先考慮10+5的策略
                {
                    cnt_five--;
                    cnt_ten--;
                }
                else if(cnt_five >= 3) cnt_five -= 3; //再考慮5+5+5的策略
                else return false;
            }
        }
        //走到這里就說明找零成功
        return true;
    }
};

4. 貪心策略證明

那么如果證明我們選擇的這種貪心策略是否正確呢？

需要用到：交換論證法

例如：

假設(shè)貪心解為 [a, b, c, d, e, f]

假設(shè)最優(yōu)解為 [e, b, c, d, a, f]

交換論證就是在不破壞最優(yōu)解的“最優(yōu)性質(zhì)”的前提下可以通過一定的調(diào)整將最優(yōu)解轉(zhuǎn)化為貪心解即可

將最優(yōu)解里面的e和a交換，這樣既沒有破壞最優(yōu)解性質(zhì)，同樣也可以將最優(yōu)解轉(zhuǎn)化為貪心解，則表示該貪心策略正確。

在本題中使用交換論證法：遇到顧客給20元，貪心解是用10元和5元進(jìn)行找零，最優(yōu)解是用三張5元進(jìn)行找零，區(qū)別就在于兩張5元和一張10元。

顧客? ? ? ? ?...? 5? ?10? ?20? ? ? ? 10? ...

貪心解? ? ?...? 0? ? 5? ?10+5? ? ? 5? ...

最優(yōu)解? ? ?...? 0? ? 5? ? 5+5+5? ?5? ...

那么在整個(gè)找零過程中，最優(yōu)解的10元存在花與不花兩種情況：

① 如果在前面或者后面的找零過程中，將10元錢花了，那么在后面花的10元錢可以將這里的5+5給替換掉，此時(shí)也就變成了貪心解；

② 如果在前面或者后面的找零過程中，沒有將10錢花掉，那么就可以用沒花掉的10元錢替換掉這里的5+5，此時(shí)也變成了貪心解。

所以通過交換論證法證明了最優(yōu)解可以在不改變最優(yōu)條件的性質(zhì)下變成貪心解，所以證明我們的貪心策略（選擇花費(fèi)5元較少的一種方法）是正確的。

朋友們、伙計(jì)們，美好的時(shí)光總是短暫的，我們本期的的分享就到此結(jié)束，欲知后事如何，請聽下回分解~，最后看完別忘了留下你們彌足珍貴的三連喔，感謝大家的支持！??????文章來源地址http://www.zghlxwxcb.cn/news/detail-833222.html

到了這里，關(guān)于【貪心算法】：LeetCode860.檸檬水找零的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！