英文网站建设 招标,阿里巴巴网站服务内容,网站盈利模式,天津建设工程信息网怎么投标水果成篮 .题目链接题目详情题目解析算法原理滑动窗口定义指针及变量进窗口判断出窗口更新结果 我的答案 . 题目链接
水果成篮
题目详情 题目解析
这道题的意思是,在一个数组中,找到一个最长的连续的子数组,并且其中包含的水果种类不超过两个 left和right刚开始都指向数组首… 水果成篮 .题目链接题目详情题目解析算法原理滑动窗口定义指针及变量进窗口判断出窗口更新结果 我的答案 . 题目链接
水果成篮
题目详情 题目解析
这道题的意思是,在一个数组中,找到一个最长的连续的子数组,并且其中包含的水果种类不超过两个 left和right刚开始都指向数组首元素,right向右移动,对数组进行遍历,记录水果种类(left与right之间) 如图:在left与right之间,此时刚好超过两个种类的水果,此时需要将left进行右移 left右移后有两种结果:
水果种类不变 此时right不动水果种类减少 此时right需要继续向右进行遍历数组,直到水果种类再次超过两个 每次满足水果种类不超过2的时候,需要更新left与right之间的长度,即子数组的最大长度 上述过程,两个指针都会向右移动,即滑动窗口模型,因此,下面我们使用滑动窗口来解决这道题
算法原理
滑动窗口 定义指针及变量
首先,滑动窗口需要两个指针,left和right,都需要对数组进行从左往右的遍历,因此,初始值都为0 还需要一个用来记录水果种类的变量,这里可以使用HashMap容器,还可以使用数组来模拟容器,这里我们使用HashMap容器来实现 除此之外,我们还需要定义一个变量,用来记录当前子数组的最大长度
进窗口
这里的进窗口,即将right当前的水果加入到容器中,并将其在容器中的个数加一
判断
判断容器中水果的种类,是否大于2
出窗口
将left所在的水果,在容器中的个数减一 当eft所在的水果个数为0时,让left所在的水果从容器中移除 left往右移动一位
更新结果
当满足容器中水果种类不超过2的时候,对子数组最大长度进行实时更新
我的答案
class Solution {public int totalFruit(int[] f) {//使用容器统计水果种类MapInteger,Integer fruits new HashMap();//定义指针int ret 0;for(int left 0,right 0;rightf.length;right){//进窗口fruits.put(f[right],fruits.getOrDefault(f[right],0)1);//判断while(fruits.size()2){//出窗口int out f[left];fruits.put(out, fruits.get(out)-1);//更新水果种类if(fruits.get(f[left])0){fruits.remove(f[left]);}left;}//更新最大子数组长度retMath.max(ret,right-left1);}return ret;}
}
