LeetCode 904. 水果成篮

题目链接

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

题目解析

在你去摘水果的时候,你当前只能拥有两种种类的水果,若想拿第三种水果,就需要发下前两种水果中的一种。

法一:滑动窗口+哈希表(未优化版本)

我们使用哈希表来记录当前水果出现的次数,当哈希表中已经有两种水果的时候,下次再摘第三种水果,就应该将前面的水果进行拿出,直到当前种类恢复到两种为止。使用滑动窗口思想,遍历到之后就进窗口,当种类超过2时就从左边进行出窗口,然后每次遍历的结尾去获取最长的子串长度。 

class Solution 
{
public:int totalFruit(vector<int>& f) {int n=f.size();int ret=INT_MIN;// 定义一个哈希表unordered_map<int,int> hash;for(int left=0,right=0;right<n;right++){// 进窗口// 记录当前水果和增加该水果出现的次数hash[f[right]]++;// 若此时种类大于2while(hash.size()>2){// 出窗口hash[f[left]]--;// 如果当前种类的水果已经减为0了,那么应该删除该元素if(hash[f[left]]==0)hash.erase(f[left]);// 更新窗口left++;}// 更新结果ret=max(ret,right-left+1);}return ret;}
};

法二:滑动窗口+哈希表(优化版本)

我们利用一个数组来代替unordered_map,来减少空间的开辟,并且使用一个变量来记录当前的水果种类。

class Solution 
{
public:int totalFruit(vector<int>& f) {int n=f.size();int ret=INT_MIN;// 定义一个哈希表int hash[100001]={0};for(int left=0,right=0,count=0;right<n;right++){// 进窗口// 记录当前水果和增加该水果出现的次数hash[f[right]]++;if(hash[f[right]]==1) count++;// 若此时种类大于2while(count>2){// 出窗口hash[f[left]]--;// 如果当前种类的水果已经减为0了,那么应该删除该元素if(hash[f[left]]==0) count--;// 更新窗口left++;}// 更新结果ret=max(ret,right-left+1);}return ret;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/124753.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

怎么把pdf转换成jpg图片?

怎么把pdf转换成jpg图片&#xff1f;在工作中&#xff0c;如果我们收到无法修改编辑的PDF文件&#xff0c;可能会遇到一些困难。尤其是当平台或网站只支持JPG图片格式&#xff0c;而领导又要求我们将pdf文件改为JPG格式时&#xff0c;情况就更为棘手了。这对于我们打工一族来说…

CSS基础

一、选择器 1.1 元素选择器&#xff1a; 指定元素统一格式 p {text_align: center;}1.2 id选择器&#xff1a; 当我们想精准找到某元素的时候要就id选择器 /* id选择器使用 # 来定义 */ #para1{ text-align:center;}1.3 class选择器&#xff1a; 多个元素统一类型 /* cl…

XCon2023 | 聚铭网络受邀出席并发表“安全运营中心的应用及发展”主题演讲

作为国内信息安全领域“历史最悠久、举办规模最大、知名度最高”的闭门型技术峰会&#xff0c;2023年XCon安全焦点信息安全峰会&#xff08;XFocus Information Security Conference&#xff09;在8月30日于北京盛大召开&#xff0c;本次大会以“链无境皆可能”为主题&#xff…

索尼 toio™应用创意开发征文|toio俄罗斯方块游戏

目录 引言 摘要 创意简述 准备工作&#xff5c;手工开始 代码编写&#xff5c;合理集成 使用体验&#xff5c;近乎奇妙 引言 索尼toio™编程机器人是一款引领技术创新的产品&#xff0c;为开发者提供了一个全新的编程和创造平台。toio™的设计旨在将技术、塑性和乐趣融为…

深度解读智能媒体服务的重组和进化

统一“顶设”的智能媒体服务。 邹娟&#xff5c;演讲者 大家好&#xff0c;首先欢迎各位来到LVS的阿里云专场&#xff0c;我是来自阿里云视频云的邹娟。我本次分享的主题为《从规模化到全智能&#xff1a;智能媒体服务的重组与进化》。 本次分享分为以上四部分&#xff0c;一是…

论数据库的种类

摘要 数据库是现代信息管理和数据存储的重要工具&#xff0c;几乎在各个领域都有广泛应用。不同类型的数据库适用于不同的应用场景和需求。本文将介绍几种常见的数据库种类&#xff0c;并探讨它们的特点和适用范围。 正文 一、关系型数据库&#xff08;RDBMS&#xff09; 关…

2023高教社杯数学建模E题思路代码 - 黄河水沙监测数据分析

# 1 赛题 E 题 黄河水沙监测数据分析 黄河是中华民族的母亲河。研究黄河水沙通量的变化规律对沿黄流域的环境治理、气候变 化和人民生活的影响&#xff0c; 以及对优化黄河流域水资源分配、协调人地关系、调水调沙、防洪减灾 等方面都具有重要的理论指导意义。 附件 1 给出了位…

[.NET学习笔记] - Thread.Sleep与Task.Delay在生产中应用的性能测试

场景 有个Service类&#xff0c;自己在内部实现生产者/消费者模式。即多个指令输入该服务后对象后&#xff0c;Service内部有专门的消费线程执行传入的指令。每个指令的执行间隔为1秒。这里有两部分组成&#xff0c; 工作线程的载体。new Thread与Task.Run。执行等待的方法。…

Map,List,Set 等集合以及底层数据结构

文章目录 概述一、Collection接口&#xff08;1&#xff09;List列表 —— 有序、值可重复&#xff08;2&#xff09;Set 集 —— 值不可重复 二、Map接口&#xff08;1&#xff09;HashMap —— 无序1、取模法2、Hash碰撞冲突3、解决Hash冲突 &#xff08;2&#xff09;HashTa…

2023 大学生数学建模竞赛-C题-第一问

题目&#xff1a; 在生鲜商超中&#xff0c;一般蔬菜类商品的保鲜期都比较短&#xff0c;且品相随销售时间的增加而变差&#xff0c; 大部分品种如当日未售出&#xff0c;隔日就无法再售。因此&#xff0c;商超通常会根据各商品的历史销售和需 求情况每天进行补货。 由于商超销…

优先发展非化石能源

生态兴则文明兴。面对气候变化、环境风险挑战、能源资源约束等日益严峻的全球问题&#xff0c;中国树立人类命运共同体理念&#xff0c;促进经济社会发展全面绿色转型&#xff0c;努力推动本国能源清洁低碳发展。 智慧光伏遮阳伞&#xff0c;搭配座椅设置智能补给休息区&#x…

如何选择靠谱的全景平台?VR全景加盟从哪方面对比?

VR全景行业经过近几年的发展&#xff0c;已经逐渐普及开来&#xff0c;线下各个行业都有实体商家开始引入VR全景去做营销宣传推广了。不少老板也意识到线上线下双渠道的重要性&#xff0c;而VR全景的存在就刚好满足各行各业的需求&#xff0c;从这一点不难看出&#xff0c;VR全…

(其他) 剑指 Offer 65. 不用加减乘除做加法 ——【Leetcode每日一题】

❓ 剑指 Offer 65. 不用加减乘除做加法 难度&#xff1a;简单 写一个函数&#xff0c;求两个整数之和&#xff0c;要求在函数体内不得使用 “”、“-”、“*”、“/” 四则运算符号。 示例: 输入: a 1, b 1 输出: 2 提示&#xff1a; a, b 均可能是负数或 0结果不会溢出 …

记录获取蓝鲸智云token的过程

一、使用python脚本获取蓝鲸智云token python版本环境&#xff1a;3.11 # -*- coding: utf-8 -*- import requestsdef get_user_token(domain,user,password):模拟用户登录&#xff0c;并返回 bk_token 和 bk_csrftokenBK_PAAS_HOST domainUSERNAME userPASSWORD password…

xargs如何保留文本中的引号

如果文本中有引号&#xff0c;直接用xargs管道操作的话&#xff0c;引号会丢失&#xff0c;如下 该如何保留每一行文本中的引号呢&#xff0c;需要用到xargs的-d选项&#xff0c;设置一个分隔符&#xff0c;这里可以选用换行符来分割 顺便多来一条&#xff0c;直接将文本参数作…

SpringBoot项目启动时预加载

SpringBoot项目启动时预加载 Spring Boot是一种流行的Java开发框架&#xff0c;它提供了许多方便的功能来简化应用程序的开发和部署。其中一个常见的需求是在Spring Boot应用程序启动时预加载一些数据或执行一些初始化操作。 1. CommandLineRunner 和 ApplicationRunner Spri…

视频融合平台EasyCVR综合管理平台加密机授权报错invalid character是什么原因

视频融合平台EasyCVR综合管理平台具备视频融合汇聚能力&#xff0c;作为安防视频监控综合管理平台&#xff0c;它支持多协议接入、多格式视频流分发&#xff0c;可支持的主流标准协议有国标GB28181、RTSP/Onvif、RTMP等&#xff0c;以及支持厂家私有协议与SDK接入&#xff0c;包…

Ubuntu安装NVIDIA显卡驱动

目录 0. 引言1. 方法1 - 使用系统自带渠道安装2. 方法2 - 手动安装2.1. 卸载原有显卡驱动2.2. 安装显卡驱动2.3. 补救措施 0. 引言 \qquad 第一次入坑的建议看一下这部分。如果说要问我什么时候应该给Ubuntu装显卡驱动&#xff0c;我建议新系统用户第一件事就是安装显卡驱动&am…

江苏移动基于OceanBase稳步创新推进核心数据库分布式升级

*本文首发自《中国电信业》 数字经济时代&#xff0c;数据库作为企业核心数据存储、处理、挖潜等方面的关键载体&#xff0c;重要性日益凸显。对于运营商而言&#xff0c;数据库具有行业用户数量多、访问数量多、业务复杂度高、数据安全性高、响应要求性高以及需要 7*24 小时服…