C++怎么实现水果装入果篮问题

这篇文章主要介绍“C++怎么实现水果装入果篮问题”，在日常操作中，相信很多人在C++怎么实现水果装入果篮问题问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”C++怎么实现水果装入果篮问题”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！

水果装入果篮

先来看第一种，使用一个 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;
    }
};

到此，关于“C++怎么实现水果装入果篮问题”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注亿速云网站，小编会继续努力为大家带来更多实用的文章！