這道題目其實考察的就是你對滑動窗口的知識的掌握,這道題的話你可以用hashmap或者數組來求解,現在的網上的題解也大部分是這種答案,我自己也寫過這2個,但是我又寫了一個比較容易讓沒有學hashmap的人理解的一種解法,不過這個寫法要求考慮的特殊情況比較多我也把各種特殊情況一一列舉出來了。
我的思路就是定義2個變量來存放2種水果樹(x,y),然后通過滑動窗口的思路去改變其中的水果樹即可
1.當水果總類少于2種,可以直接輸出數組長度(fruits.length)
2.當水果種類只有一種,并且個數大于2個,直接輸出fruits.length
3.這種我把細分成了2種,其實也就是滑動窗口的算法,不過變得復雜一點罷了,當你找到與x,y不同的水果樹時,你得重置這個x,y
3.1當你找到不同的水果樹的前面那顆水果樹是y類的,你可以通過while來使得i來變化,然后重置x,和y即可
比如 1 2 2 3 3
當j走到3的時候,將x,y都變,這其中的為啥要分2種我想你看完下面這個你就知道我為什么要分為2種了。
3.2當你找到不同的水果樹的前面那顆水果樹是x類的,你可以通過while來使得i來變化,然后重置y即可,這里x是不需要變化的因為x本身就是在y的前面,所以不需要改變
比如1 0 1 4 1 4 1 2 3
上面的幾個例子你可以自己試著去運行一下你就知道了
廢話多說了,題如下(依舊是力扣的)
你正在探訪一家農場,農場從左到右種植了一排果樹。這些樹用一個整數數組 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 <= 105
0 <= fruits[i] < fruits.length
題解源碼如下:
class Solution { public int totalFruit(int[] fruits) { int i=0,j=0,x,y,len=0; if(fruits.length <= 2) return fruits.length;//1 x = fruits[j++]; while((j<fruits.length)&&x==fruits[j])j++;//2 if(j==fruits.length) return fruits.length; y = fruits[j]; while(j < fruits.length){ if(fruits[j]!=x&&fruits[j]!=y) { i = j - 1; if(fruits[i]==y) {//3.1 while (fruits[i] == y) i--; i++; x = fruits[i]; y = fruits[j]; } else {//3.2 while (fruits[i] == x) i--; i++; y = fruits[j]; } } else j++; len = Math.max(len,j-i); } return len; } }
中間斷了2天是因為入黨積極分子的事情,這周周末補齊,當菜鳥的第4天2022-03-28,每日奮斗一題,加油
浙公網安備 33010602011771號