当前位置: 首页 > news >正文

数组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. 水果成篮 你正在探访一家农场&#xff0c;农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示&#xff0c;其中 fruits[i] 是第 i 棵树上的水果 种类 。 你想要尽可能多地收集水果。然而&#xff0c;农场的主人设定了一些严格的规矩&#xff0c…...

【C++杂货店】类和对象(上)

【C杂货店】类和对象&#xff08;上&#xff09; 一、面向过程和面向对象初步认识二、类的引入三、类的定义四、类的访问限定符及封装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 错误&#xff1a;不支持将“name”作为别名 SELECT real_name name FROM doc_user 加上 在关键词上加上 “” 示例&#xff1a; SELECT real_name "name" FROM do…...

都用HTTPS了,还能被查出浏览记录?

最近&#xff0c;群里一个刚入职的小伙因为用公司电脑访问奇怪的网站&#xff0c;被约谈了。他很困惑 —— 访问的都是HTTPS的网站&#xff0c;公司咋知道他访问了啥&#xff1f; 实际上&#xff0c;由于网络通信有很多层&#xff0c;即使加密通信&#xff0c;仍有很多途径暴露…...

vi配置文件.vimrc内容示例

1、.vimrc配置文件介绍 &#xff08;1&#xff09;.vimrc是vi编辑器的配置文件&#xff0c;里面可以对vi编译器做个性化配置&#xff1b; &#xff08;2&#xff09;.vimrc在用户目录下&#xff0c;每个用户有一个&#xff0c;类似于.bashrc文件&#xff0c;将下面的配置文件内…...

MacOS上的Pip和Python升级指南

在MacOS系统上&#xff0c;保持Pip和Python版本的最新状态对于顺利进行Python开发至关重要。通过升级Pip和Python&#xff0c;你可以享受到最新的功能、修复的bug以及提升的开发效率。本文将为你提供在MacOS上升级Pip和Python的详细指南&#xff0c;助你打造更强大的开发环境。…...

VB6.0实现修改EXE程序的图标

当你给一家公司做技术支持的时候&#xff0c;需求各种各样的&#xff0c;其中今天遇到就是要修改某个程序的图标&#xff0c;代码实现如下。 // q1016058890 群 214016721 //注 意&#xff1a;这个方法貌似只对有些EXE文件有效&#xff0c;这不是万能的方法&#xff0c;此…...

Python 编程基础 | 第二章-基础语法 | 2.3、for 语句

一、for 语句 1、循环语句 for循环的语法格式如下&#xff1a; for iterating_var in sequence:statements(s)例如&#xff1a; for ch in "hello world":print(ch)fruits ["banana", "apple", "mango"] for fruit in fruits:print(…...

linux下解决tomcat错误问题

错误一&#xff1a; Linux下Tomcat启动报错&#xff1a;Neither the JAVA_HOME nor the JRE_HOME environment variable is defined 原因&#xff1a;可能是Linux环境变了&#xff0c;需要在catalina.sh文件里指定JDK路径 解决方式&#xff1a; 在/bin/catalina.sh配置文件中加…...

PMP证书的价值如何?

2022年开始&#xff0c;PMP考试启用了新考纲&#xff0c;不光考试内容进行了大刀阔斧的改革&#xff0c;出题方式也进行了更新。除原有的PMBOK6和PMBOK7主考教材外&#xff0c;还增加了一本《敏捷实践指南》。 别小看新加的这本书&#xff0c;它虽然与PMBOK代表的预测法属于完…...

linux上mysql数据备份(全量备份策略+增量备份策略)

执行备份策略前&#xff0c;先做好scp命令的准备 解决思路&#xff1a; 生成SSH公钥/私钥后&#xff0c;您需要将公钥添加到服务器上&#xff0c;从而使服务器可以使用该公钥来验证您的身份。 生成SSH公钥/私钥的命令为 ssh-keygen -t rsa -b 4096什么都不用输入&#xff0c…...

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 的主要功能&#xff1f; 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()排序函数&#xff08;c&#xff09;一、原理二、使用方法&#xff08;一&#xff09;头文件&#xff08;二&#xff09;使用语法1.方式一&#xff08;默认&#xff09;2.方式二&#xff1a;定义升序或降序3.方式三&#xff1a;自定义 sort()排序函数&#xff08…...

如何评估测试用例的优先级?

评估测试用例的优先级&#xff0c;有助于我们及早发现和解决可能对系统稳定性和功能完整性产生重大影响的问题&#xff0c;助于提高测试质量&#xff0c;提高用户满意度。 如果没有做好测试用例的优先级评估&#xff0c;往往容易造成对系统关键功能和高风险场景测试的忽略&…...

510758-28-8,用于标记蛋白质和酶的配体TBTA

产品简介&#xff1a;Tris(benzyltriazolylmethyl)amine (TBTA)是一种配体&#xff0c;能作为生化工具用于标记蛋白质和酶。 CAS号&#xff1a;510758-28-8 中文名&#xff1a;三[(1-苄基-1H-1,2,3-三唑-4-基)甲基]胺 英文名&#xff1a;TBTA 化学式&#xff1a;C30H30N10…...

Jtti:云服务器ftp不能访问端口如何解决

如果您的云服务器上的FTP服务无法访问端口&#xff0c;可能有多种原因导致这种情况。以下是一些可能的解决方法&#xff1a; 检查FTP服务状态&#xff1a; 首先&#xff0c;请确保您的FTP服务器正在运行。您可以使用以下命令来检查FTP服务器的状态&#xff0c;具体命令可能因FT…...

web vue 项目 Docker化部署

Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段&#xff1a; 构建阶段&#xff08;Build Stage&#xff09;&#xff1a…...

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15

缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下&#xff1a; struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

渲染学进阶内容——模型

最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...

el-switch文字内置

el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

拉力测试cuda pytorch 把 4070显卡拉满

import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试&#xff0c;通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小&#xff0c;增大可提高计算复杂度duration: 测试持续时间&#xff08;秒&…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 在 GPU 上对图像执行 均值漂移滤波&#xff08;Mean Shift Filtering&#xff09;&#xff0c;用于图像分割或平滑处理。 该函数将输入图像中的…...