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