904. Fruit Into Baskets

​​​​​​904. Fruit Into Baskets

题目如上,代码如下

第一种

class Solution {
public:
    int totalFruit(vector& fruits) {
        int ans = 0 ,i = 0;
        map count;
        for (int j = 0; j < fruits.size(); ++j) {
            count[fruits[j]]++;
            while (count.size() >= 3) {
                count[fruits[i]]--;
                if (count[fruits[i]]==0) {
                    count.erase(fruits[i]);
                }
                i++;
            }
            ans = max(j - i + 1, ans);
        }
        return ans;
    }
private:
    int max(int a, int b){
        return a > b ? a : b;
    }
};

 另一种

class Solution {
public:
    int totalFruit(vector& fruits) {
        vector blockLefts;
        for (int i = 0; i < fruits.size(); ++i) {
            if (i == 0 || fruits[i] != fruits[i - 1]) {
                blockLefts.push_back(i);
            }
        }
        blockLefts.push_back(fruits.size());
        int ans = 0, i = 0;
        while (true) {
            bool flag = false;
            set types;
            int weight = 0;
            for (int j = i; j < blockLefts.size() - 1; j++) {
                types.insert(fruits[blockLefts[j]]);
                weight += blockLefts[j + 1] - blockLefts[j];
                if (types.size() >= 3) {
                    i = j - 1;
                    flag = true;
                    break;
                }
                ans = max(ans, weight);
            }
            if(flag)
                continue;
            break;
        }
        return ans;
    }

private:
    int max(int a,int b){
        return a > b ? a : b;
    }
};

这是leetcode官网的题解,但它没有c++版本的,所以我把它的代码翻译成了c++版本的

然后我说下我对这个题目的理解吧,其实这两种方法在我这里都是一样的,我个人感觉这道题其实也是一个双指针的运用吧,只是第一种第二种表现形式不一样,但认真看的话,快指针其实就是j,慢指针其实就是i,第一种方法利用map来统计目前使用的元素的总数,如果总数大于2,那么就要删除最开始的元素,也就是让i进行移动,并且顺便删除对应的value值,这里不能直接用value跳值,因为value可能是前后的总和.第二种大体也是这种思路,唯一的区别其实就是利用set进行元素个数的管理