当前位置: 首页> 游戏> 攻略 > 艺术字体在线生成器免费转换器_推广普通话宣传周活动方案_网站建设方案书模板_seo零基础培训

艺术字体在线生成器免费转换器_推广普通话宣传周活动方案_网站建设方案书模板_seo零基础培训

时间:2025/7/11 15:48:03来源:https://blog.csdn.net/hlyd520/article/details/143983249 浏览次数:0次
艺术字体在线生成器免费转换器_推广普通话宣传周活动方案_网站建设方案书模板_seo零基础培训

题目链接:

904.水果成篮


文章目录

    • 题目链接:
    • 题目描述:
    • 解法
    • C++ 算法代码:
    • 图解


题目描述:

c53c92023b7b4d8e1049bf73fda3a08f


解法

解法一:暴力枚举+哈希表

找到所有的子数组,然后比较大小。

e1e2640189c7635db9237376b5564d0c

解法二:滑动窗口+哈希表

本质上就是在数组中找到最长的一个子数组,子数组里面不超过两种水果。

当右端水果进入窗口的时候,用哈希表统计这个水果的频次。这个水果进来后,判断哈希表的大小。

kinds有两种情况:

  1. kinds不变

    若当前区间满足kinds=2,那么left向右移动,有可能仍然包含两种水果。

    此时,right不需要后移

d8937793b9205b090bdaf7dd933ef739

  1. kinds变小

    若当前区间满足kinds=2,那么left向右移动,有可能只包含一种水果。

    此时,right需要后移

解法:

  1. left=0,right=0
  2. 进窗口
  3. 判断,出窗口
  4. 更新结果
  • 如果大小超过 2:说明窗口内水果种类超过了两种。那么就从左侧开始依次将水果划出窗口,直到哈希表的大小小于等于 2,然后更新结果;

  • 如果没有超过 2:说明当前窗口内水果的种类不超过两种,直接更新结果 ret


C++ 算法代码:

class Solution 
{public:int totalFruit(vector<int>& f) {unordered_map<int, int> hash; // 使用哈希表(unordered_map)统计窗口内出现了多少种水果int ret = 0;for(int left = 0, right = 0; right < f.size(); right++){hash[f[right]]++; // 将当前水果类型 f[right] 添加到哈希表中,并更新其计数//f[right] 表示当前遍历到的水果类型//hash[f[right]]:这部分代码访问哈希表 hash 中键为 f[right] 的元素。例如,hash[1] 表示水果类型 1 在当前窗口内的出现次数。//hash[f[right]]++:这行代码将 hash[f[right]] 的值增加 1。这意味着在当前窗口中,水果类型 f[right] 的出现次数增加了一次。while(hash.size() > 2) // 如果哈希表的大小超过 2,意味着当前窗口内包含超过两种水果类型{// 从当前窗口的左边界移除水果类型 f[left]hash[f[left]]--;if(hash[f[left]] == 0)// 如果该水果类型的计数为 0,则从哈希表中移除该键hash.erase(f[left]);left++;// 移动左边界指针 left,向右移动以缩小窗口}ret = max(ret, right - left + 1);// 更新结果 ret 为当前窗口长度与之前记录的最大长度中的较大值// 窗口长度计算为 right - left + 1}return ret;}
};

图解

例如:f=[1,2,1,2,3,2,3,3]

  1. left = 0, right = 0

a8ad3819b41ba3ef65a94618bc9414fa

  1. f[0]1类型的果树,hash[f[0]]++后等于1,说明在当前窗口中,水果类型为1的出现次数为1次。

    hash.size()=1ret = max(ret, right - left + 1)=1right++

  2. f[1]2类型的果树,hash[f[1]]++后等于1,说明在当前窗口中,水果类型为2的出现次数为1次。

    hash.size()=2,ret = max(ret, right - left + 1)=2right++

b62f2e41c2ba77dbd03e2c5739610ff0

  1. f[2]1类型的果树,hash[f[2]]++后等于2,说明在当前窗口中,水果类型为1的出现次数为2次。

    hash.size()=2,ret = max(ret, right - left + 1)=3right++

6780d24d23fb9c2cb105ebc7cabf4c0b

  1. f[3]2类型的果树,hash[f[3]]++后等于2,说明在当前窗口中,水果类型为2的出现次数为2次。

    hash.size()=2,ret = max(ret, right - left + 1)=4right++

9929352820d983cf4ff58b370b0f3a9b

  1. f[4]3类型的果树,hash[f[4]]++后等于1,说明在当前窗口中,水果类型为3的出现次数为1次。

    hash.size()=3>2进入循环。

    hash[f[left]]--;// 从当前窗口的左边界移除水果类型 f[left]

    此时hash[1类型的果树]=1,继续hash[f[left]]--;

    此时hash[2类型的果树]=1,继续hash[f[left]]--;

    此时hash[1类型的果树]=0,执行

    if(hash[f[left]] == 0),hash.erase(f[left]);

    ret = max(ret, right - left + 1)=4right++

eae9e32f90d0ba339048c6920b656a88

  1. 后面步骤差不多,不过多赘述了。
关键字:艺术字体在线生成器免费转换器_推广普通话宣传周活动方案_网站建设方案书模板_seo零基础培训

版权声明:

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

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

责任编辑: