[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

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

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

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;
    }
};

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

• 若當(dāng)前字符和前一個字符相同，繼續(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 時，i=5,6 的時候，都是繼續(xù)循環(huán)，當(dāng)i加到7時，跳出了循環(huán)，而此時正確答案應(yīng)為 [2,1,1,1] 這4個數(shù)字，而我們的結(jié)果 res 只更新到了 [5,3,5] 這3個數(shù)字，所以我們最后要判斷 n - left 和結(jié)果 res 的大小。

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

解法三：

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

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++實現(xiàn)LeetCode(904.水果裝入果籃)的文章就介紹到這了,更多相關(guān)C++實現(xiàn)水果裝入果籃內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！