算法刷题:水果成篮

本文主要是介绍算法刷题:水果成篮，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

.

题目链接

水果成篮

题目详情

题目解析

这道题的意思是,在一个数组中,找到一个最长的连续的子数组,并且其中包含的水果种类不超过两个

left和right刚开始都指向数组首元素,right向右移动,对数组进行遍历,记录水果种类(left与right之间)
如图:在left与right之间,此时刚好超过两个种类的水果,此时需要将left进行右移
left右移后有两种结果:

1. 水果种类不变 此时right不动
2. 水果种类减少 此时right需要继续向右进行遍历数组,直到水果种类再次超过两个
   每次满足水果种类不超过2的时候,需要更新left与right之间的长度,即子数组的最大长度
   上述过程,两个指针都会向右移动,即滑动窗口模型,因此,下面我们使用滑动窗口来解决这道题

算法原理

滑动窗口

定义指针及变量

首先,滑动窗口需要两个指针,left和right,都需要对数组进行从左往右的遍历,因此,初始值都为0
还需要一个用来记录水果种类的变量,这里可以使用HashMap容器,还可以使用数组来模拟容器,这里我们使用HashMap容器来实现
除此之外,我们还需要定义一个变量,用来记录当前子数组的最大长度

进窗口

这里的进窗口,即将right当前的水果加入到容器中,并将其在容器中的个数加一

判断

判断容器中水果的种类,是否大于2

出窗口

将left所在的水果,在容器中的个数减一
当eft所在的水果个数为0时,让left所在的水果从容器中移除
left往右移动一位

更新结果

当满足容器中水果种类不超过2的时候,对子数组最大长度进行实时更新

我的答案

class Solution {public int totalFruit(int[] f) {//使用容器统计水果种类Map<Integer,Integer> fruits = new HashMap<>();//定义指针int ret = 0;for(int left = 0,right = 0;right<f.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++;}//更新最大子数组长度ret=Math.max(ret,right-left+1);}return ret;}
}

这篇关于算法刷题:水果成篮的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---