当前位置: 首页> 科技> 互联网 > Leetcode每日刷题之904.水果成篮

Leetcode每日刷题之904.水果成篮

时间:2025/7/11 1:09:27来源:https://blog.csdn.net/2301_80689220/article/details/141438965 浏览次数:2次

1.题目解析

本题的题目要求较长,不过理解起来较为简单,就是在给定数组内找出最长子数组,并且该最长子数组只能有两种数字,最后返回该符合条件的最长子数组的长度即可

题目来源:904.水果成篮 

2.算法原理

本题的核心是找出符合条件的最长子数组,首先想到的一定是暴力枚举所有符合条件的子数组最后找出最长的即可

在经过优化的算法就是"滑动窗口"算法,

1.即使用两个指针,让right指针不断向后遍历而left指针不动,在left-right这一段窗口内加入数据称为入窗口

2.当窗口内数字的种类超过两种则开始出窗口,也就是left指针移动而right指针不动,直到窗口中数字种类为2种,这时更新子数组长度

3.这里使用数组hash模仿哈希表,因为由题目可知数组中数字范围小于10^5,所以创建一个hash[100001]即可,然后使用kinds变量统计窗口内数字种类

4.hash[100001]存储每个数字出现的次数,当出窗口时某个数字出现次数为0则将种类kinds--即可,最后更新长度直到找出最长符合子数组的长度即可

3.代码展示

class Solution {
public:int totalFruit(vector<int>& fruits) {int n = fruits.size();int hash[100001] = { 0 };int len = 0;for(int left = 0,right = 0,kinds = 0;right < n;right++){if(hash[fruits[right]] == 0){kinds++;}hash[fruits[right]]++;while(kinds > 2){hash[fruits[left]]--;if(hash[fruits[left]] == 0){kinds--;}left++;}len = max(len,right - left + 1);}return len;}
};

 

关键字:Leetcode每日刷题之904.水果成篮

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: