本题链接水果成篮
第一步：了解题意
我就按照实例1来进行对这题的理解。
1代表种类类型，这个数组里面有2个种类类型 ps:种类1和种类2 ，只不过种类1是有2个水果，种类2有一个水果，共计3个水果。
本题需要解答：收集水果的最大数目.
但是前提条件：
我们只有2个篮子，每个篮子里只能装1种类型，但是篮子里的数量是不限制的。每采摘一次，将会可以向右移动到下一棵树，并继续采摘，不能跳过一棵树2个篮子表示着我们只能容纳2个类型的，出现第3类型的苹果，我们就直接结束采摘
就按实例3来表示：fruits[1，2，3，2，2]
1，2，遇到3的时候，这就是我们遇到的第三种类型水果了，那么我们就需要停止，这时候就可以记录一次苹果的数量2，其实后面就不用看了。
然后就从2开始，因为2，3是2种类型就可以继续采摘，大于2才是不行的，所以2，3，2，2，一直是可以的，因为都是种类2，相当于同一种类型，所以苹果数量是4，这时候最大的采摘数量是4.
第二步：算法思路
以后我们遇到一些题目记录一些重复值个数，如果超过几个数或者不能重复，就需要将这个值存入到哈希表中（其实就是值得映射到数组中去）
大部分题目都是从 暴力枚举 然后一步一步的优化得到的，所以
第一种解法：暴力枚举+哈希
首先定义2个指针，都是在0位置出发。
暴力枚举中的第二步，每一次都得清空hash中的值，我们就会觉得很繁琐，那么如何优化呢？
第二种解法：滑动窗口+哈希
滑动窗口的模板：
1.left=0,right=0;
2.进窗口
3.判断
4.出窗口
更新结果（这是是在上面的4个步骤中根据题目的不同来穿插的）
2.进窗口
实际上，就是让right的值存入到hash表中（hash表其实就是一个一维数组）
3.判断
我们上面再了解题意的时候已经写上了（种类超过2种的就得停止采摘）
所以判断的条件就是是否超过2种种类。
4.出窗口
出窗口建立在判断的时候的 ，判断了超过2种类型，我们就得出窗口，left对应的值就得--，如果减到0了我们就得给种类-1，知道减到种类=2，left++,我们就可以继续进行滑动窗口的步骤。
5.更新结果
结果是只要判断结果kinds<2就可以更新结果。
第三步：代码实现
class Solution {
public:
int totalFruit(vector
int hash[100001]={0};//统计窗口中出现了多少种水果
int ret=0;
for(int left=0,right=0,kinds=0;right { if(hash[fruits[right]]==0) kinds++; hash[fruits[right]]++;//进窗口 while(kinds>2)//判断 { //出窗口 hash[fruits[left]]--;//left对应的值一直-- if(hash[fruits[left]]==0) kinds--;//直到-到0就给种类-- left++; } ret=max(ret,right-left+1); } return ret; } }; 我永远走在提升自己的路上~ 好文阅读
您阅读本篇文章共花了：
发表评论