果篮水果搭配技巧

C++实现LeetCode（904.⽔果装⼊果篮）

[LeetCode]ntoBaskets⽔果装⼊果篮

Inarowoftrees,the`i`-thtreeproducesfruitwithtype`tree[i]`.

Youstartatanytreeofyourchoice,thenrepeatedlyperformthefollowingsteps:

annot,stop.

eisnotreetotheright,stop.

Notethatyoudonothaveanychoiceaftertheinitialchoiceofstartingtree:youmustperformstep1,thenstep2,thenbackto

step1,thenstep2,andsoonuntilyoustop.

Youhavetwobaskets,andeachbasketcancarryanyquantityoffruit,butyouwanteachbaskettoonlycarryonetypeoffruit

each.

Whatisthetotalamountoffruityoucancollectwiththisprocedure?

Example1:

Input:[1,2,1]

Output:3

Explanation:Wecancollect[1,2,1].

Example2:

Input:[0,1,2,2]

Output:3

Explanation:Wecancollect[1,2,2].Ifwestartedatthefirsttree,wewouldonlycollect[0,1].

Example3:

Input:[1,2,3,2,2]

Output:4

Explanation:Wecancollect[2,3,2,2].Ifwestartedatthefirsttree,wewouldonlycollect[1,2].

Example4:

Input:[3,3,3,1,2,1,1,2,3,3,4]

Output:5

Explanation:Wecancollect[1,2,1,1,2].Ifwestartedatthefirsttreeortheeighthtree,wewouldonlycollect4

fruits.

Note:

1.1<=<=40000

2.0<=tree[i]<

classSolution{

public:

inttotalFruit(vector&tree){

intres=0,start=0,n=();

unordered_mapfruitCnt;

for(inti=0;i

++fruitCnt[tree[i]];

while(()>2){

if(--fruitCnt[tree[start]]==0){

(tree[start]);

}

++start;

}

res=max(res,i-start+1);

}

returnres;

}

};

我们除了⽤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，再更新结果，以此类推直⾄遍历

完整个数组，参见代码如下：

解法⼆：

classSolution{

public:

inttotalFruit(vector&tree){

intres=0,start=0,n=();

unordered_mapfruitPos;

for(inti=0;i

fruitPos[tree[i]]=i;

while(()>2){

if(fruitPos[tree[start]]==start){

(tree[start]);

}

++start;

}

res=max(res,i-start+1);

}

returnres;

}

};

后来⼜在⽹上看到了⼀种解法，这种解法是维护⼀个滑动窗⼝slidingwindow，指针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个的话，还是需要⽤上⾯两种解法。

解法三：

classSolution{

public:

inttotalFruit(vector&tree){

intres=0,left=0,right=-1,n=();

for(inti=1;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;

}

returnmax(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，参见代码如下：

解法四：

classSolution{

public:

inttotalFruit(vector&tree){

intres=0,cur=0,cntB=0,a=0,b=0;

for(intfruit: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);

}

returnres;

}

};

Github同步地址:

参考资料：

到此这篇关于C++实现LeetCode(904.⽔果装⼊果篮)的⽂章就介绍到这了,更多相关C++实现⽔果装⼊果篮内容请搜索以前的⽂

章或继续浏览下⾯的相关⽂章希望⼤家以后多多⽀持！