数组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…...
8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂
蛋白质结合剂(如抗体、抑制肽)在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上,高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术,但这类方法普遍面临资源消耗巨大、研发周期冗长…...
[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?
论文网址:pdf 英文是纯手打的!论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误,若有发现欢迎评论指正!文章偏向于笔记,谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...
论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)
笔记整理:刘治强,浙江大学硕士生,研究方向为知识图谱表示学习,大语言模型 论文链接:http://arxiv.org/abs/2407.16127 发表会议:ISWC 2024 1. 动机 传统的知识图谱补全(KGC)模型通过…...
leetcodeSQL解题:3564. 季节性销售分析
leetcodeSQL解题:3564. 季节性销售分析 题目: 表:sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...
Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)
参考官方文档:https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java(供 Kotlin 使用) 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...
LeetCode - 199. 二叉树的右视图
题目 199. 二叉树的右视图 - 力扣(LeetCode) 思路 右视图是指从树的右侧看,对于每一层,只能看到该层最右边的节点。实现思路是: 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...
人机融合智能 | “人智交互”跨学科新领域
本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...
JavaScript基础-API 和 Web API
在学习JavaScript的过程中,理解API(应用程序接口)和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能,使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...
如何更改默认 Crontab 编辑器 ?
在 Linux 领域中,crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用,用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益,允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...
C语言中提供的第三方库之哈希表实现
一. 简介 前面一篇文章简单学习了C语言中第三方库(uthash库)提供对哈希表的操作,文章如下: C语言中提供的第三方库uthash常用接口-CSDN博客 本文简单学习一下第三方库 uthash库对哈希表的操作。 二. uthash库哈希表操作示例 u…...
