数组07-滑动窗口、HashMap
LeetCode——904. 水果成篮
你正在探访一家农场,农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示,其中 fruits[i] 是第 i 棵树上的水果 种类 。
你想要尽可能多地收集水果。然而,农场的主人设定了一些严格的规矩,你必须按照要求采摘水果:
-
你只有 两个 篮子,并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
-
你可以选择任意一棵树开始采摘,你必须从 每棵 树(包括开始采摘的树)上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次,你将会向右移动到下一棵树,并继续采摘。
-
一旦你走到某棵树前,但水果不符合篮子的水果类型,那么就必须停止采摘。
给你一个整数数组 fruits ,返回你可以收集的水果的 最大 数目。
示例 1:
输入:fruits = [1,2,1] 输出:3 解释:可以采摘全部 3 棵树。
示例 2:
输入:fruits = [0,1,2,2] 输出:3 解释:可以采摘 [1,2,2] 这三棵树。 如果从第一棵树开始采摘,则只能采摘 [0,1] 这两棵树。
示例 3:
输入:fruits = [1,2,3,2,2] 输出:4 解释:可以采摘 [2,3,2,2] 这四棵树。 如果从第一棵树开始采摘,则只能采摘 [1,2] 这两棵树。
示例 4:
输入:fruits = [3,3,3,1,2,1,1,2,3,3,4] 输出:5 解释:可以采摘 [1,2,1,1,2] 这五棵树。
提示:
-
1 <= fruits.length <= 105 -
0 <= fruits[i] < fruits.length
分析:
1.题意可知,结果是找到只包含两种水果类别的最大长度子数组。算法用滑动窗口。
2.当种类大于2的时候,是新一轮迭代的开始。怎么判断窗口左边界是需要考虑的地方.如下两种情况:
-
[1,1,1,1,2,2,2,2,2,1,1,1,3]
-
[1,1,1,2,2,2,2,3]
要满足题意,那么窗口内只能有两种水果类别,可以使用hashmap进行存储和判断,当种类大于2的时候,左边界上的元素不断地移除,直到满足窗口内只有两种水果类别的条件。
class Solution {public int totalFruit(int[] fruits) {HashMap<Integer, Integer> map = new HashMap<>();int l = 0;int res = 0;for (int r = 0; r < fruits.length; r++) {map.put(fruits[r], map.getOrDefault(fruits[r], 0) + 1);while (map.size() > 2){map.put(fruits[l], map.get(fruits[l]) - 1);if (map.get(fruits[l]) == 0) {map.remove(fruits[l]);}l++;}res = Math.max(res, r - l + 1);}return res;}
}相关文章:
数组07-滑动窗口、HashMap
LeetCode——904. 水果成篮 你正在探访一家农场,农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示,其中 fruits[i] 是第 i 棵树上的水果 种类 。 你想要尽可能多地收集水果。然而,农场的主人设定了一些严格的规矩,…...
【C++杂货店】类和对象(上)
【C杂货店】类和对象(上) 一、面向过程和面向对象初步认识二、类的引入三、类的定义四、类的访问限定符及封装4.1 访问限定符4.2 封装 五、类的作用域六、类的实例化七、类对象模型7.1 类对象的存储规则7.2 例题7.3结构体内存对齐规则 八、this指针8.2 t…...
K8S笔记
...
MySQL关于日期函数的使用-笔记
韩老师笔记 select current_time select CURRENT_DATE create table mes ( id int, content VARCHAR(255), send_time DATETIME ) select * from mes; insert into mes values(1,北京,CURRENT_DATE) insert into mes (id,send_time) values(2,CURRENT_TIME) insert into mes v…...
【postgresql 】 ERROR: “name“ is not supported as an alias
org.postgresql.util.PSQLException: ERROR: "name" is not supported as an alias 错误:不支持将“name”作为别名 SELECT real_name name FROM doc_user 加上 在关键词上加上 “” 示例: SELECT real_name "name" FROM do…...
都用HTTPS了,还能被查出浏览记录?
最近,群里一个刚入职的小伙因为用公司电脑访问奇怪的网站,被约谈了。他很困惑 —— 访问的都是HTTPS的网站,公司咋知道他访问了啥? 实际上,由于网络通信有很多层,即使加密通信,仍有很多途径暴露…...
vi配置文件.vimrc内容示例
1、.vimrc配置文件介绍 (1).vimrc是vi编辑器的配置文件,里面可以对vi编译器做个性化配置; (2).vimrc在用户目录下,每个用户有一个,类似于.bashrc文件,将下面的配置文件内…...
MacOS上的Pip和Python升级指南
在MacOS系统上,保持Pip和Python版本的最新状态对于顺利进行Python开发至关重要。通过升级Pip和Python,你可以享受到最新的功能、修复的bug以及提升的开发效率。本文将为你提供在MacOS上升级Pip和Python的详细指南,助你打造更强大的开发环境。…...
VB6.0实现修改EXE程序的图标
当你给一家公司做技术支持的时候,需求各种各样的,其中今天遇到就是要修改某个程序的图标,代码实现如下。 // q1016058890 群 214016721 //注 意:这个方法貌似只对有些EXE文件有效,这不是万能的方法,此…...
Python 编程基础 | 第二章-基础语法 | 2.3、for 语句
一、for 语句 1、循环语句 for循环的语法格式如下: for iterating_var in sequence:statements(s)例如: for ch in "hello world":print(ch)fruits ["banana", "apple", "mango"] for fruit in fruits:print(…...
linux下解决tomcat错误问题
错误一: Linux下Tomcat启动报错:Neither the JAVA_HOME nor the JRE_HOME environment variable is defined 原因:可能是Linux环境变了,需要在catalina.sh文件里指定JDK路径 解决方式: 在/bin/catalina.sh配置文件中加…...
PMP证书的价值如何?
2022年开始,PMP考试启用了新考纲,不光考试内容进行了大刀阔斧的改革,出题方式也进行了更新。除原有的PMBOK6和PMBOK7主考教材外,还增加了一本《敏捷实践指南》。 别小看新加的这本书,它虽然与PMBOK代表的预测法属于完…...
linux上mysql数据备份(全量备份策略+增量备份策略)
执行备份策略前,先做好scp命令的准备 解决思路: 生成SSH公钥/私钥后,您需要将公钥添加到服务器上,从而使服务器可以使用该公钥来验证您的身份。 生成SSH公钥/私钥的命令为 ssh-keygen -t rsa -b 4096什么都不用输入,…...
PHP实现DFA算法,查找关键词
# 添加关键词 到全局字典dict里面 protected function addWord($strWord) {$len mb_strlen($strWord,UTF-8);$curNode &$this->dict;for ($index 0; $index < $len; $index) {$word mb_substr($strWord, $index, 1, UTF-8);if (!isset($curNode[$word])) {$curNo…...
JTS:08 JTS图形相交
这里写目录标题 版本JTS disjoint intersects俩个图形不相交俩个图形 边相交俩个图形 内部相交俩个图形 点相交 版本 org.locationtech.jts:jts-core:1.19.0 链接: github JTS disjoint intersects 不相交的 九交模型FF*FF**** 相交的 九交模型 [T********] [*T*******] [**…...
深挖 ThreadLocal 底层原理?它有什么用?学会之后手撕面试官
目录 1. ThreadLocal 的主要功能? 2. ThreadLocal 代码举例 3. ThreadLocal 源码分析 3.1 ThreadLocal 的 get 方法源码解析 3.2 ThreadLocal 的 set 方法源码解析 3.3 ThreadLocal 的 createMap 方法源码解析 3.4 ThreadLocal 的 set 方法总结 4. 为什么En…...
sort()排序函数(c++)
文章目录 sort()排序函数(c)一、原理二、使用方法(一)头文件(二)使用语法1.方式一(默认)2.方式二:定义升序或降序3.方式三:自定义 sort()排序函数(…...
如何评估测试用例的优先级?
评估测试用例的优先级,有助于我们及早发现和解决可能对系统稳定性和功能完整性产生重大影响的问题,助于提高测试质量,提高用户满意度。 如果没有做好测试用例的优先级评估,往往容易造成对系统关键功能和高风险场景测试的忽略&…...
510758-28-8,用于标记蛋白质和酶的配体TBTA
产品简介:Tris(benzyltriazolylmethyl)amine (TBTA)是一种配体,能作为生化工具用于标记蛋白质和酶。 CAS号:510758-28-8 中文名:三[(1-苄基-1H-1,2,3-三唑-4-基)甲基]胺 英文名:TBTA 化学式:C30H30N10…...
Jtti:云服务器ftp不能访问端口如何解决
如果您的云服务器上的FTP服务无法访问端口,可能有多种原因导致这种情况。以下是一些可能的解决方法: 检查FTP服务状态: 首先,请确保您的FTP服务器正在运行。您可以使用以下命令来检查FTP服务器的状态,具体命令可能因FT…...
华为云AI开发平台ModelArts
华为云ModelArts:重塑AI开发流程的“智能引擎”与“创新加速器”! 在人工智能浪潮席卷全球的2025年,企业拥抱AI的意愿空前高涨,但技术门槛高、流程复杂、资源投入巨大的现实,却让许多创新构想止步于实验室。数据科学家…...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...
多场景 OkHttpClient 管理器 - Android 网络通信解决方案
下面是一个完整的 Android 实现,展示如何创建和管理多个 OkHttpClient 实例,分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...
【机器视觉】单目测距——运动结构恢复
ps:图是随便找的,为了凑个封面 前言 在前面对光流法进行进一步改进,希望将2D光流推广至3D场景流时,发现2D转3D过程中存在尺度歧义问题,需要补全摄像头拍摄图像中缺失的深度信息,否则解空间不收敛…...
Ascend NPU上适配Step-Audio模型
1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统,支持多语言对话(如 中文,英文,日语),语音情感(如 开心,悲伤)&#x…...
《基于Apache Flink的流处理》笔记
思维导图 1-3 章 4-7章 8-11 章 参考资料 源码: https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...
多种风格导航菜单 HTML 实现(附源码)
下面我将为您展示 6 种不同风格的导航菜单实现,每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...
稳定币的深度剖析与展望
一、引言 在当今数字化浪潮席卷全球的时代,加密货币作为一种新兴的金融现象,正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而,加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下,稳定…...
Pinocchio 库详解及其在足式机器人上的应用
Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库,专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性,并提供了一个通用的框架&…...
处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的
修改bug思路: 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑:async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...
