C++实现LeetCode(904.水果装入果篮)

[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