seo网站建设价格,优化型网站是模板,ui设计稿,安徽移动互联网开发代码#xff1a;
class Solution {public int totalFruit(int[] fruits) {int lengthfruits.length;int []fruitNumsnew int[length1]; //用于记录各个种类摘了多少个水果int count0; //用于记录当前采摘了几种水果int sum0; //用于记录当前共摘了多少水果for(int left0…
代码
class Solution {public int totalFruit(int[] fruits) {int lengthfruits.length;int []fruitNumsnew int[length1]; //用于记录各个种类摘了多少个水果int count0; //用于记录当前采摘了几种水果int sum0; //用于记录当前共摘了多少水果for(int left0,right0;rightfruits.length;right){//将 right 指针指向的数据进窗口int infruits[right]; //要采摘的水果//判断当前采摘的水果是否是之前没有的种类if(fruitNums[in]0){count;//判断水果种类是否超过了2while (count2){//将 left 指针指向的数据出窗口int outfruits[left];fruitNums[out]--;if(fruitNums[out]0){count--;}}}fruitNums[in];sumMath.max(sum,right-left1);}return sum;}
}
题解 首先我们需要理清题目需求 1.只有 两个 篮子并且每个篮子只能装 单一类型 的水果说明只能选两个类型的水果 2.可以选择任意一棵树开始采摘必须从 每棵 树包括开始采摘的树上 恰好摘一个水果 每采摘一次你将会向右移动到下一棵树并继续采摘一旦你走到某棵树前但水果不符合篮子的水果类型那么就必须停止采摘。说明必须连续采摘直到水果类型超过两种为止。 通过连续二字我们很容易想到该题目需要我们找到一个符合要求的子数组首先子数组中的数字种类不能超过 2 其次我们要找到符合条件的最长子数组取得他的长度 我们很容易想到的暴力解法就是遍历出所有的子数组找到数字种类不能超过 2并且长度最长的那一个 对于查找子数组的相关问题通常我们会想到采用滑动窗口的方法来解决用示例3来说明fruits [1,2,3,2,2] 首先需要遍历找出符合条件的子数组让 L 和 R 指针指向下标为 0 的位置L 和 R 指针之间便是我们当前要讨论的子数组我们用一个哈希表 fruitNums 来记录篮子里已经装的水果种类和数量用 count 来记录当前篮子里已经有的水果种类当 R 指针指向 1 时我们就需要在哈希表中添加 key 1value1 的信息代表篮子中有 1 个种类为 1 的水果由于之前哈希表中没有种类 1水果的相关信息代表篮子中的水果种类增加 1 此时 count 1记录当前的水果数量 1
1 2 3 2 2
L
R 让 R 指针向右移动再添加一个水果到篮子中在哈希表中添加 key 2value1 的信息由于之前哈希表中没有种类 2 水果的相关信息代表篮子中的水果种类增加 1 此时 count 2,记录当前的水果数量 2
1 2 3 2 2
L R 让 R 指针向右移动再添加一个水果到篮子中在哈希表中添加 key 3value1 的信息由于之前哈希表中没有种类 3 水果的相关信息代表篮子中的水果种类增加 1 此时 count 3 2,两个篮子装不下了代表以 L 指针为首的子数组讨论完毕现在让 L 指针向右移动
1 2 3 2 2
L R L 指针向右移动后哈希表中的 key 1 对应的 value 值减 1value 0代表篮子中少了一种水果count减 1 为 2记录当前的水果数量 2 这里就存在一个问题当 L 指针向右移动是否需要 R 指针回到 L 指针所在的位置从头遍历子数组答案是不需要 因为此时 L 指针和 R 指针之间不包括 R 指针的水果种类肯定是小于等于 2 的只有加上 R 指针指向的水果水果种类才可以多于 2 即使 R 指针回到 L 指针所在的位置后面还是会移动到当前位置
1 2 3 2 2 L R 后面就一直循环上述操作即可
