[LeetCode] 904. Fruit Into Baskets 水果裝入果籃

In a row of trees, the `i`-th tree produces fruit with type `tree[i]`.

You start at any tree of your choice, then repeatedly perform the following steps:

1. Add one piece of fruit from this tree to your baskets.  If you cannot, stop.
2. Move to the next tree to the right of the current tree.  If there is no tree to the right, stop.

Note that you do not have any choice after the initial choice of starting tree: you must perform step 1, then step 2, then back to step 1, then step 2, and so on until you stop.

You have two baskets, and each basket can carry any quantity of fruit, but you want each basket to only carry one type of fruit each.

What is the total amount of fruit you can collect with this procedure?

Example 1:

Input: [1,2,1]
Output: 3
Explanation: We can collect [1,2,1].

Example 2:

Input: [0,1,2,2]
Output: 3
Explanation: We can collect [1,2,2]. If we started at the first tree, we would only collect [0, 1]. 

Example 3:

Input: [1,2,3,2,2]
Output: 4
Explanation: We can collect [2,3,2,2]. If we started at the first tree, we would only collect [1, 2]. 

Example 4:

Input: [3,3,3,1,2,1,1,2,3,3,4]
Output: 5 
Explanation: We can collect [1,2,1,1,2]. If we started at the first tree or the eighth tree, we would only collect 4 fruits. 

Note:

1. 1 <= tree.length <= 40000
2. 0 <= tree[i] < tree.length

這道題說(shuō)是給了我們一排樹(shù)，每棵樹(shù)產(chǎn)的水果種類是 tree[i]，說(shuō)是現(xiàn)在有兩種操作，第一種是將當(dāng)前樹(shù)的水果加入果籃中，若不能加則停止；第二種是移動(dòng)到下一個(gè)樹(shù)，若沒(méi)有下一棵樹(shù)，則停止。現(xiàn)在我們有兩個(gè)果籃，可以從任意一個(gè)樹(shù)的位置開(kāi)始，但是必須按順序執(zhí)行操作一和二，問(wèn)我們最多能收集多少個(gè)水果。說(shuō)實(shí)話這道題的題目描述確實(shí)不太清晰，博主看了很多遍才明白意思，論壇上也有很多吐槽的帖子，但實(shí)際上這道題的本質(zhì)就是從任意位置開(kāi)始，若最多只能收集兩種水果，問(wèn)最多能收集多少個(gè)水果。那么再進(jìn)一步提取，其實(shí)就是最多有兩個(gè)不同字符的最長(zhǎng)子串的長(zhǎng)度，跟之前那道 [Longest Substring with At Most Two Distinct Characters](http://www.cnblogs.com/grandyang/p/5185561.html) 一模一樣，只不過(guò)換了一個(gè)背景，代碼基本都可以直接使用的，博主感覺(jué)這樣出題有點(diǎn)不太好吧，完全重復(fù)了。之前那題的四種解法這里完全都可以使用，先來(lái)看第一種，使用一個(gè) HashMap 來(lái)記錄每個(gè)水果出現(xiàn)次數(shù)，當(dāng) HashMap 中當(dāng)映射數(shù)量超過(guò)兩個(gè)的時(shí)候，我們需要?jiǎng)h掉一個(gè)映射，做法是滑動(dòng)窗口的左邊界 start 的水果映射值減1，若此時(shí)減到0了，則刪除這個(gè)映射，否則左邊界右移一位。當(dāng)映射數(shù)量回到兩個(gè)的時(shí)候，用當(dāng)前窗口的大小來(lái)更新結(jié)果 res 即可，參見(jiàn)代碼如下：
解法一：

class Solution {
public:
    int totalFruit(vector<int>& tree) {
        int res = 0, start = 0, n = tree.size();
        unordered_map<int, int> fruitCnt;
        for (int i = 0; i < n; ++i) {
            ++fruitCnt[tree[i]];
            while (fruitCnt.size() > 2) {
                if (--fruitCnt[tree[start]] == 0) {
                    fruitCnt.erase(tree[start]);
                }
                ++start;
            }
            res = max(res, i - start + 1);
        }
        return res;
    }
};

我們除了用 HashMap 來(lái)映射字符出現(xiàn)的個(gè)數(shù)，我們還可以映射每個(gè)數(shù)字最新的坐標(biāo)，比如題目中的例子 [0,1,2,2]，遇到第一個(gè)0，映射其坐標(biāo)0，遇到1，映射其坐標(biāo)1，當(dāng)遇到2時(shí)，映射其坐標(biāo)2，每次我們都判斷當(dāng)前 HashMap 中的映射數(shù)，如果大于2的時(shí)候，那么需要?jiǎng)h掉一個(gè)映射，我們還是從 start=0 時(shí)開(kāi)始向右找，看每個(gè)字符在 HashMap 中的映射值是否等于當(dāng)前坐標(biāo) start，比如0，HashMap 此時(shí)映射值為0，等于 left 的0，那么我們把0刪掉，start 自增1，再更新結(jié)果，以此類推直至遍歷完整個(gè)數(shù)組，參見(jiàn)代碼如下：
解法二：

class Solution {
public:
    int totalFruit(vector<int>& tree) {
        int res = 0, start = 0, n = tree.size();
        unordered_map<int, int> fruitPos;
        for (int i = 0; i < n; ++i) {
            fruitPos[tree[i]] = i;
            while (fruitPos.size() > 2) {
                if (fruitPos[tree[start]] == start) {
                    fruitPos.erase(tree[start]);
                }
                ++start;
            }
            res = max(res, i - start + 1);
        }
        return res;
    }
};

后來(lái)又在網(wǎng)上看到了一種解法，這種解法是維護(hù)一個(gè)滑動(dòng)窗口 sliding window，指針 left 指向起始位置，right 指向 window 的最后一個(gè)位置，用于定位 left 的下一個(gè)跳轉(zhuǎn)位置，思路如下：

• 若當(dāng)前字符和前一個(gè)字符相同，繼續(xù)循環(huán)。

• 若不同，看當(dāng)前字符和 right 指的字符是否相同：

  • 若相同，left 不變，右邊跳到 i - 1。

  • 若不同，更新結(jié)果，left 變?yōu)?right+1，right 變?yōu)?i - 1。

最后需要注意在循環(huán)結(jié)束后，我們還要比較結(jié)果 res 和 n - left 的大小，返回大的，這是由于如果數(shù)組是 [5,3,5,2,1,1,1]，那么當(dāng) left=3 時(shí)，i=5,6 的時(shí)候，都是繼續(xù)循環(huán)，當(dāng)i加到7時(shí)，跳出了循環(huán)，而此時(shí)正確答案應(yīng)為 [2,1,1,1] 這4個(gè)數(shù)字，而我們的結(jié)果 res 只更新到了 [5,3,5] 這3個(gè)數(shù)字，所以我們最后要判斷 n - left 和結(jié)果 res 的大小。

另外需要說(shuō)明的是這種解法僅適用于于不同字符數(shù)為2個(gè)的情況，如果為k個(gè)的話，還是需要用上面兩種解法。

解法三：

class Solution {
public:
    int totalFruit(vector<int>& tree) {
        int res = 0, left = 0, right = -1, n = tree.size();
        for (int i = 1; i < n; ++i) {
            if (tree[i] == tree[i - 1]) continue;
            if (right >= 0 && tree[right] != tree[i]) {
                res = max(res, i - left);
                left = right + 1;
            }
            right = i - 1;
        }
        return max(n - left, res);
    }
};

還有一種不使用 HashMap 的解法，這里我們使用若干個(gè)變量，其中 cur 為當(dāng)前最長(zhǎng)子數(shù)組的長(zhǎng)度，a和b為當(dāng)前候選的兩個(gè)不同的水果種類，cntB 為水果b的連續(xù)個(gè)數(shù)。我們遍歷所有數(shù)字，假如遇到的水果種類是a和b中的任意一個(gè)，那么 cur 可以自增1，否則 cntB 自增1，因?yàn)槿羰切滤N類的話，默認(rèn)已經(jīng)將a種類淘汰了，此時(shí)候選水果由類型b和這個(gè)新類型水果構(gòu)成，所以當(dāng)前長(zhǎng)度是 cntB+1。然后再來(lái)更新 cntB，假如當(dāng)前水果種類是b的話，cntB 自增1，否則重置為1，因?yàn)?cntB 統(tǒng)計(jì)的就是水果種類b的連續(xù)個(gè)數(shù)。然后再來(lái)判斷，若當(dāng)前種類不是b，則此時(shí)a賦值為b， b賦值為新種類。最后不要忘了用 cur 來(lái)更新結(jié)果 res，參見(jiàn)代碼如下：
解法四：

class Solution {
public:
    int totalFruit(vector<int>& tree) {
        int res = 0, cur = 0, cntB = 0, a = 0, b = 0;
        for (int fruit : tree) {
            cur = (fruit == a || fruit == b) ? cur + 1 : cntB + 1;
            cntB = (fruit == b) ? cntB + 1 : 1;
            if (b != fruit) {
                a = b; b = fruit;
            }
            res = max(res, cur);
        }
        return res;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/904

參考資料：

https://leetcode.com/problems/fruit-into-baskets/

https://leetcode.com/problems/fruit-into-baskets/discuss/170740/Sliding-Window-for-K-Elements

https://leetcode.com/problems/fruit-into-baskets/discuss/170745/Problem%3A-Longest-Subarray-With-2-Elements

https://leetcode.com/problems/fruit-into-baskets/discuss/170808/Java-Longest-Subarray-with-atmost-2-Distinct-elements

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(904.水果裝入果籃)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)水果裝入果籃內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論