C++實現LeetCode(904.水果裝入果籃)

Posted on by

[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

這道題說是給瞭我們一排樹，每棵樹產的水果種類是 tree[i]，說是現在有兩種操作，第一種是將當前樹的水果加入果籃中，若不能加則停止；第二種是移動到下一個樹，若沒有下一棵樹，則停止。現在我們有兩個果籃，可以從任意一個樹的位置開始，但是必須按順序執行操作一和二，問我們最多能收集多少個水果。說實話這道題的題目描述確實不太清晰，博主看瞭很多遍才明白意思，論壇上也有很多吐槽的帖子，但實際上這道題的本質就是從任意位置開始，若最多隻能收集兩種水果，問最多能收集多少個水果。那麼再進一步提取，其實就是最多有兩個不同字符的最長子串的長度，跟之前那道 [Longest Substring with At Most Two Distinct Characters](http://www.cnblogs.com/grandyang/p/5185561.html) 一模一樣，隻不過換瞭一個背景，代碼基本都可以直接使用的，博主感覺這樣出題有點不太好吧，完全重復瞭。之前那題的四種解法這裡完全都可以使用，先來看第一種，使用一個 HashMap 來記錄每個水果出現次數，當 HashMap 中當映射數量超過兩個的時候，我們需要刪掉一個映射，做法是滑動窗口的左邊界 start 的水果映射值減1，若此時減到0瞭，則刪除這個映射，否則左邊界右移一位。當映射數量回到兩個的時候，用當前窗口的大小來更新結果 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 來映射字符出現的個數，我們還可以映射每個數字最新的坐標，比如題目中的例子 [0,1,2,2]，遇到第一個0，映射其坐標0，遇到1，映射其坐標1，當遇到2時，映射其坐標2，每次我們都判斷當前 HashMap 中的映射數，如果大於2的時候，那麼需要刪掉一個映射，我們還是從 start=0 時開始向右找，看每個字符在 HashMap 中的映射值是否等於當前坐標 start，比如0，HashMap 此時映射值為0，等於 left 的0，那麼我們把0刪掉，start 自增1，再更新結果，以此類推直至遍歷完整個數組，參見代碼如下：
解法二：

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

後來又在網上看到瞭一種解法，這種解法是維護一個滑動窗口 sliding window，指針 left 指向起始位置，right 指向 window 的最後一個位置，用於定位 left 的下一個跳轉位置，思路如下：

  • 若當前字符和前一個字符相同，繼續循環。

  • 若不同，看當前字符和 right 指的字符是否相同：

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

    • 若不同，更新結果，left 變為 right+1，right 變為 i – 1。

最後需要註意在循環結束後，我們還要比較結果 res 和 n – left 的大小，返回大的，這是由於如果數組是 [5,3,5,2,1,1,1]，那麼當 left=3 時，i=5,6 的時候，都是繼續循環，當i加到7時，跳出瞭循環，而此時正確答案應為 [2,1,1,1] 這4個數字，而我們的結果 res 隻更新到瞭 [5,3,5] 這3個數字，所以我們最後要判斷 n – left 和結果 res 的大小。

另外需要說明的是這種解法僅適用於於不同字符數為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 為當前最長子數組的長度，a和b為當前候選的兩個不同的水果種類，cntB 為水果b的連續個數。我們遍歷所有數字，假如遇到的水果種類是a和b中的任意一個，那麼 cur 可以自增1，否則 cntB 自增1，因為若是新水果種類的話，默認已經將a種類淘汰瞭，此時候選水果由類型b和這個新類型水果構成，所以當前長度是 cntB+1。然後再來更新 cntB，假如當前水果種類是b的話，cntB 自增1，否則重置為1，因為 cntB 統計的就是水果種類b的連續個數。然後再來判斷，若當前種類不是b，則此時a賦值為b， b賦值為新種類。最後不要忘瞭用 cur 來更新結果 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

到此這篇關於C++實現LeetCode(904.水果裝入果籃)的文章就介紹到這瞭,更多相關C++實現水果裝入果籃內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：