904. 水果成篮(滑动窗口)

2023-10-21 21:44
文章标签 窗口 滑动 水果 904 成篮

本文主要是介绍904. 水果成篮(滑动窗口),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

一、题目

二、代码


一、题目

 力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

二、代码

  • 题目实质:找出一个最长的子数组的长度,要求子数组中不超过两种类型的水果
  • 哈希表+双指针 
class Solution {
public:int totalFruit(vector<int>& fruits) {int _MaxCount = INT_MIN;int _Sum = 0;//总的水果种类vector<int>FruitType(100001, 0);//存放水果的种类vector<int>FruitCount(100001, 0);//不同种类水果的数量for (int left = 0, right = 0; right < fruits.size(); right++){++FruitCount[fruits[right]];//进窗口,对应种类的水果数量+1if (FruitType[fruits[right]] == 0)//如果某种水果的数量是0{FruitType[fruits[right]] = 1;_Sum++;//总的水果种类+1}if (_Sum <= 2){_MaxCount = max(_MaxCount, right - left + 1);//更新continue;}if (_Sum > 2)//判断,水果种类大于2{_MaxCount = max(_MaxCount, right - left);//更新(次数fruits[right]处是第3种类型,所以左闭右开)int mark = fruits[left];while (fruits[left] == mark)//left右移,将连续相同的种类出窗口{++left;--FruitCount[fruits[left - 1]];}if (FruitCount[fruits[left - 1]] == 0)//当移动到某种类水果数量为0的时候{FruitType[fruits[left - 1]] = 0;//将不存在对应的种类--_Sum;//总的水果种类-1}}}return _MaxCount;}
};

改进:

class Solution {
public:int totalFruit(vector<int>& f) {int _MaxCount = INT_MIN;unordered_map<int, int> hash;//下标表示水果的种类,存放某种类水果数量for (int left = 0, right = 0; right < f.size(); right++){++hash[f[right]];//进窗口while (hash.size() > 2){//出窗口--hash[f[left]];//某种类水果数量-1if (hash[f[left]] == 0)//如果某种类水果数量为0,则删除该种类{hash.erase(f[left]);}left++;}_MaxCount = max(_MaxCount, right - left + 1);}return _MaxCount;}
};

这篇关于904. 水果成篮(滑动窗口)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/257165

相关文章

使用JS/Jquery获得父窗口的几个方法(笔记)

<pre name="code" class="javascript">取父窗口的元素方法:$(selector, window.parent.document);那么你取父窗口的父窗口的元素就可以用:$(selector, window.parent.parent.document);如题: $(selector, window.top.document);//获得顶级窗口里面的元素 $(

904.水果成篮

题目 链接:leetcode链接 思路分析(滑动窗口) 读完题目,很明显,这个题目需要我们寻找一个最长子数组,使得这个子数组里面最多存在两种不同的数字,很容易联想到使用滑动窗口。 另外,需要使用hash表来记录区间内的不同种水果的个数 首先还是left,right = 0; 进窗口:right进哈希表 判断:哈希表的size > 2,就需要出窗口 出窗口:hash[left]–的同时,

专题二_滑动窗口_算法专题详细总结

目录 滑动窗口,引入: 滑动窗口,本质:就是同向双指针; 1.⻓度最⼩的⼦数组(medium) 1.解析:给我们一个数组nums,要我们找出最小子数组的和==target,首先想到的就是暴力解法 1)暴力: 2)优化,滑动窗口: 1.进窗口 2.出窗口 3.更新值 2.⽆重复字符的最⻓⼦串(medium) 1)仍然是暴力解法: 2)优化: 进窗口:hash[s[rig

hot100刷题第1-9题,三个专题哈希,双指针,滑动窗口

求满足条件的子数组,一般是前缀和、滑动窗口,经常结合哈希表; 区间操作元素,一般是前缀和、差分数组 数组有序,更大概率会用到二分搜索 目前已经掌握一些基本套路,重零刷起leetcode hot 100, 套路题按套路来,非套路题适当参考gpt解法。 一、梦开始的地方, 两数之和 class Solution:#注意要返回的是数组下标def twoSum(self, nums: Lis

主窗口的设计与开发(二)

主窗口的设计与开发(二) 前言         在上一集当中,我们完成了主窗口的初始化,主窗口包括了左中右三个区域。我们还完成了对左窗口的初始化,左窗口包括了用户头像、会话标签页按钮、好友标签页按钮以及好友申请标签页按钮。对于切换每个标签页,我们还做了初始化信号槽的内容。最后我们将整个MainWidget类设置为单例模式。         那么这一集我们将继续完成主窗口的设计与开发,这一集我

QtC++截图支持窗口获取

介绍 在截图工具中你会发现,接触到窗口后会自动圈出目标窗口,个别强大一点的还能进行元素识别可以自动圈出元素,那么今天简单分析一下QTc++如何获取窗口并圈出当前鼠标下的窗口。 介绍1.如何获取所有窗口2.比较函数3.实现窗口判断 结尾 1.如何获取所有窗口 1.我们需要调用windows接口EnumWindowsProc回调函数来获取所有顶级窗口,需要包含windows.

运行.bat文件,如何在Dos窗口里面得到该文件的路径

把java代码打包成.jar文件,编写一个.bat文件,执行该文件,编译.jar包;(.bat,.jar放在同一个文件夹下) 运行.bat文件,如何在Dos窗口里面得到该文件的路径,并运行.jar文件: echo 当前盘符:%~d0 echo 当前路径:%cd% echo 当前执行命令行:%0 echo 当前bat文件路径:%~dp0 echo 当前bat文件短路径:%~sdp0 nc

类codepen的实现可拖拽窗口demo

首先说下思想 flex或者其他布局方式,实现左右分割布局,主盒子宽度100%,左右布局中包含一个分割条(可在布局容器中,也可以单独定义)为分隔条绑定鼠标点击事件,为document绑定鼠标移动事件和鼠标放开事件,通过监听鼠标移动事件和上一个状态保存下来的鼠标位置作对比,判断当前鼠标移动方向(往左还是往右)然后计算当前鼠标位置和鼠标点击位置的距离,来计算左右容器的变化,然后通过dom的方式设置宽度

【leetcode详解】考试的最大困扰度(滑动窗口典例)

实战总结: sum += answerKey[right] == c; 经典操作,将判断语句转化为0, 1接收来计数//大问题分解: 对'T'还是'F'做修改, 传参为c//滑动窗口: 遍历, 维护left& right指向 及 c的个数, 更新不知从何下手写代码时:考虑先写好第一次的,然后以此为基础补充代码以适后续情况 题面: 解题感受: 思路总体好想, 实现略有挑战。 思路分析:

笔试强训,[NOIP2002普及组]过河卒牛客.游游的水果大礼包牛客.买卖股票的最好时机(二)二叉树非递归前序遍历

目录 [NOIP2002普及组]过河卒 牛客.游游的水果大礼包 牛客.买卖股票的最好时机(二) 二叉树非递归前序遍历 [NOIP2002普及组]过河卒 题里面给的提示很有用,那个马的关系,后面就注意,dp需要作为long的类型。 import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息publ