目錄

1.題目

2.分析

方法1:暴力枚舉

方法2:暴力解法的優化:滑動窗口

代碼

方法3:優化方法2:使用數組充當哈希表

方法4:四個變量分別充當籃子和籃子中水果的個數(最快!!!)

代碼

容易忽略的點

---

1.題目

https://leetcode.cn/problems/fruit-into-baskets/

你正在探訪一家農場，農場從左到右種植了一排果樹。這些樹用一個整數數組 fruits 表示，其中 fruits[i] 是第 i 棵樹上的水果 種類 。

你想要盡可能多地收集水果。然而，農場的主人設定了一些嚴格的規矩，你必須按照要求采摘水果：

• 你只有 兩個 籃子，并且每個籃子只能裝 單一類型 的水果。每個籃子能夠裝的水果總量沒有限制。
• 你可以選擇任意一棵樹開始采摘，你必須從 每棵 樹（包括開始采摘的樹）上 恰好摘一個水果 。采摘的水果應當符合籃子中的水果類型。每采摘一次，你將會向右移動到下一棵樹，并繼續采摘。
• 一旦你走到某棵樹前，但水果不符合籃子的水果類型，那么就必須停止采摘。

給你一個整數數組 fruits ，返回你可以收集的水果的 最大 數目。

示例 1：

輸入：fruits = [1,2,1]
輸出：3
解釋：可以采摘全部 3 棵樹。

示例 2：

輸入：fruits = [0,1,2,2]
輸出：3
解釋：可以采摘 [1,2,2] 這三棵樹。
如果從第一棵樹開始采摘，則只能采摘 [0,1] 這兩棵樹。

示例 3：

輸入：fruits = [1,2,3,2,2]
輸出：4
解釋：可以采摘 [2,3,2,2] 這四棵樹。
如果從第一棵樹開始采摘，則只能采摘 [1,2] 這兩棵樹。

示例 4：

輸入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
輸出：5
解釋：可以采摘 [1,2,1,1,2] 這五棵樹。

提示：

• 1 <= fruits.length <= 10^5
• 0 <= fruits[i] < fruits.length

2.分析

需要使用set來統計[left,right]之間水果的種類數

方法1:暴力枚舉

class Solution {
public:int totalFruit(vector<int>& fruits) {int left=0,right=0,ret=0;for (;left<fruits.size();left++){set<int> mp;for (right=left;right<fruits.size();right++){mp.insert(fruits[right]);if (mp.size()>2)break;}       ret=max(ret,right-left);}return ret;}
};

提交結果:超時

方法2:暴力解法的優化:滑動窗口

right不用每次都從left開始枚舉,以這個為例:[1,2,1,2,3,2,3,3]

當mp.size()>2時,

left只需要向前移動,直到mp.size()2時停止移動,能減少大量無用的循環,提高運行速度

使用存儲雙關鍵字類型的map<int,int>,第一個關鍵字存儲類型,第二個關鍵字存儲每類的水果的個數

可以先mp[fruits[right]]++(進窗口),看看mp.size()有沒有超過2,如果超過,使mp[fruits[left++]]--(出窗口),如果發現減到0了,就erase(注:erase直接刪除掉節點的所有信息, 不是讓mp[x]置為0)

最后更新結果:ret=max(ret,right-left+1);

代碼

class Solution {
public:int totalFruit(vector<int>& fruits) {map<int,int> mp;int left=0,right=0,ret=0; for (;right<fruits.size();right++){mp[fruits[right]]++;while (mp.size()==3){mp[fruits[left++]]--;if (mp[fruits[left-1]]==0)mp.erase(fruits[left-1]);}ret=max(ret,right-left+1);}return ret;}
};

提交結果:

當然也可以使用unordered_map解決:

但無論是map還是unordered_map對mp多次插入和刪除比較耗時,時間復雜度較高,可以使用方法3:數組充當哈希表

方法3:優化方法2:使用數組充當哈希表

要多用一個變量kind來存儲水果種類的數量,因為1 <= fruits.length <= 10^5 使用哈希數組hash[100001]來存儲,哈希數組的特點正好符合對雙關鍵字的要求,對于種類為x的水果,其個數為hash[x]

kind++的條件:hash[fruit[right]]從0變成1

kind--的條件:hash[fruit[right]]從1變成0

class Solution {
public:int totalFruit(vector<int>& fruits) {int hash[100001]={0};int left=0,right=0,ret=0,kind=0; for (;right<fruits.size();right++){hash[fruits[right]]++;if (hash[fruits[right]]==1)kind++;while (kind==3){hash[fruits[left++]]--;if (hash[fruits[left-1]]==0)kind--;}ret=max(ret,right-left+1);}return ret;}
};

提交結果:

方法4:四個變量分別充當籃子和籃子中水果的個數(最快!!!)

bkt1存儲籃子1的水果種類數,籃子1的水果個數為bkt1_num(bkt為basket的簡寫)

bkt2存儲籃子2的水果種類數,籃子1的水果個數為bkt2_num

代碼

class Solution {
public:int totalFruit(vector<int>& fruits){int bkt1 = -1, bkt2 = -1, bkt1_num = 0, bkt2_num = 0;int left = 0, right = 0, ret = 0;for (; right < fruits.size(); right++){if (bkt1 == -1){bkt1 = fruits[right];bkt1_num++;}else if (bkt2 == -1&&fruits[right]!=bkt1){bkt2 = fruits[right];bkt2_num++;}else{if (fruits[right] == bkt1)bkt1_num++;else if (fruits[right] == bkt2)bkt2_num++;else//如果出現第三種水果{while (1){if (fruits[left] == bkt1)bkt1_num--;elsebkt2_num--;left++;if (bkt1_num == 0){bkt1 = fruits[right];bkt1_num++;break;}if (bkt2_num == 0){bkt2 = fruits[right];bkt2_num++;break;}}}}ret = max(ret, right - left + 1);}return ret;}
};

容易忽略的點

else if (bkt2 == -1&&fruits[right]!=bkt1)的fruits[right]!=bkt1不可以省,否則將無法通過[0,0,1,1]測試用例

提交結果: