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

双指针问题——求只包含两个元素的最长连续子序列(子数组)

一,题目描述

你正在探访一家农场,农场从左到右种植了一排果树。这些树用一个整数数组 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

二,题目接口

class Solution {
public:int totalFruit(vector<int>& fruits) {}
};

三,解题思路

1,统计子数组中各个元素出现的次数。

2,统计元素的类型。

3,在子数组元素类型的数量等于二时才会更新ans。

4,当这个子数组元素的类型大于二时,从左到右将元素对应的数量减一。直到某个元素的数量变为0就将元素类型的数量减一。

代码实现如下:

class Solution {
public:int totalFruit(vector<int>& fruits) {int n = fruits.size();int ans = 0;//保存答案int countType = 0;//统计元素类型数量unordered_map<int,int>hash;//哈希表统计元素的数量for(int r = 0,l = 0;r<n;r++){if(++hash[fruits[r]] == 1)//这个元素类型的数量从零到一便将类型加一{countType++;}if (countType>2)//当出现类型的数量等于3时做以下处理{while(--hash[fruits[l++]]);countType--; //当某个元素的值变为0时便将counttype减1}ans = max(ans,r-l+1);//更新最大值}return ans;}
};

相关文章:

双指针问题——求只包含两个元素的最长连续子序列(子数组)

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

Unity组件开发--短连接HTTP

1.网络请求管理器 using LitJson; using Cysharp.Threading.Tasks; using System; using System.Collections; using System.Collections.Generic; using UnityEngine; using UnityEngine.Networking; using UnityEngine.Events;using System.Web; using System.Text; using Sy…...

真正的强大,原来是不动声色的

当一个人走过了绝境&#xff0c;他就会发现&#xff0c;真正的强大&#xff0c;原来是不动声色的。 他会停止一切自证&#xff0c;不再解释&#xff0c;话越来越少&#xff0c;眼神越来越坚定。 他不再模棱两可&#xff0c;唯唯诺诺&#xff0c;而是敢于断然拒绝&#xff0c;…...

git 查看tag和创建tag以及上传tag命令

文章目录 git 查看tag和创建tag以及上传tag命令git tagtag操作常用命令 git 查看tag和创建tag以及上传tag命令 git tag 如果你达到一个重要的阶段&#xff0c;并希望永远记住那个特别的提交快照&#xff0c;你可以使用 git tag 给它打上标签。 Git 的 tag 功能是一个非常有用…...

代码随想录二刷 |二叉树 | 二叉搜索树的最小绝对差

代码随想录二刷 &#xff5c;二叉树 &#xff5c; 二叉搜索树的最小绝对差 题目描述解题思路 & 代码实现递归法迭代法 题目描述 530.二叉搜索树的最小绝对差 给你一棵所有节点为非负值的二叉搜索树&#xff0c;请你计算树中任意两节点的差的绝对值的最小值。 示例&#…...

【Linux】Linux 系统编程——tree 命令

文章目录 1. 命令概述2. 命令格式3. 常用选项4. 相关描述4.1 tree 命令安装 5. 参考示例5.1 创建树形目录5.2 使用 tree 命令查看树形目录 1. 命令概述 tree 命令用于在命令行界面以树状图形式显示目录及其子目录的内容。这个命令递归地列出所有子目录&#xff0c;并可选择显示…...

Android简单控件

1.文本显示 设置文本内容的两种方式&#xff1a; 在XML文件中通过属性 android:text 设置文本 <resources><string name"app_name">chapter03</string><string name"hello">你好&#xff0c;世界</string> </resources&…...

【Java 干货教程】Java实现分页的几种方式详解

一、前言 无论是自我学习中&#xff0c;还是在工作中&#xff0c;固然会遇到与前端搭配实现分页的功能&#xff0c;发现有几种方式&#xff0c;特此记录一下。 二、实现方式 2.1、分页功能直接交给前端实现 这种情况也是有的&#xff0c;(根据业务场景且仅仅只能用于数据量…...

关于Python里xlwings库对Excel表格的操作(三十一)

这篇小笔记主要记录如何【如何使用“Chart类”、“Api类"和“Axes函数”设置绘图区外框线型、颜色、粗细及填充颜色】。前面的小笔记已整理成目录&#xff0c;可点链接去目录寻找所需更方便。 【目录部分内容如下】【点击此处可进入目录】 &#xff08;1&#xff09;如何安…...

QML使用QCustomPlot笔记

这里在QML中使用QCustomPlot是定义一个继承自QQuickPaintedItem的类&#xff0c;它包含一个QCustomPlot对象&#xff0c;在paint函数中将这个对象转化为pixmap绘制到布局中显示。 在QML中使用QT的Widget控件也可以借鉴这个思路实现 顺便记录一下QCustomPlot的简单设置与使用。…...

【REST2SQL】06 GO 跨包接口重构代码

【REST2SQL】01RDB关系型数据库REST初设计 【REST2SQL】02 GO连接Oracle数据库 【REST2SQL】03 GO读取JSON文件 【REST2SQL】04 REST2SQL第一版Oracle版实现 【REST2SQL】05 GO 操作 达梦 数据库 对所有关系数据的操作都只有CRUD&#xff0c;采用Go 的接口interface{}重构代码…...

《NLP入门到精通》栏目导读

一、说明 栏目《NLP入门到精通》本着从简到难得台阶式学习过度。将自然语言处理得知识贯穿过来。本栏目得前导栏目是《深度学习》、《pytorch实践》&#xff0c;因此&#xff0c;读者需要一定得深度学习基础&#xff0c;才能过度到此栏目内容。 二、博客建设理念 本博客基地&am…...

C++学习笔记——类继承

目录 一、一个简单的基类 1.1封装性 1.2继承性 1.3虚函数 1.4多态性 二、基类 2.1一个简单的C基类的示例 2.2 Animal是一个基类。 三、继承 3.1概念 3.2is-a关系 3.3多态公有继承 3.4静态联编和动态联编 3.5访问控制 3.6ABC理念 一、一个简单的基类 C中的基类是一…...

ARCGIS PRO SDK 使用条件管理 Pro UI

ARCGIS PRO UI简单介绍以下&#xff1a; 第一步&#xff1a;在Config.daml中在</AddInfo>标签下加上条件<conditions>标签&#xff08;必须添加的&#xff09; <conditions><!-- 定义条件 &#xff0c;此处定义了两个--Tab 另一个为 group><insert…...

Halcon经典的边缘检测算子Sobel/Laplace/Canny

Halcon经典的边缘检测算子 文章目录 Halcon经典的边缘检测算子1. Sobel算子2. Laplace 算子3. Canny 算子4. 总结 关于边缘检测&#xff0c;有许多经典的算子&#xff0c;各大图形处理库都有各自的边缘检测算子&#xff0c;这里简要介绍几种。 1. Sobel算子 Sobel算子结合了高…...

用单片机设计PLC电路图

自记&#xff1a; 见另一篇文章&#xff0c;MOS驱动差了一个充电电容&#xff0c;栅极电容充电会有问题&#xff1b; 光耦用的直插&#xff0c;但板子用的贴片&#xff0c;此文档仅供参考 基本列出了PCB板情况&#xff0c;基础元器件&#xff0c;部分连接&#xff0c;原理等…...

【设计模式-6】建造者模式的实现与框架中的应用

建造者模式又被成为生成器模式&#xff0c;是一种使用频率比较低&#xff0c;相对复杂的创建型模式&#xff0c;在很多源码框架中可以看到建造者的使用场景&#xff0c;稍后我们会在本文末尾展示几个框架的使用案例。  建造者模式所构造的对象通常是比较复杂而且庞大的&#x…...

PositiveSSL和Sectigo的多域名证书

首先&#xff0c;我们要知道PositiveSSL是Sectigo旗下的子品牌&#xff0c;提供多种类型的SSL数字证书&#xff0c;包括DV基础型的多域名SSL证书。Sectigo的SSL证书产品同样比较丰富&#xff0c;不仅有DV基础型多域名SSL证书&#xff0c;还有OV企业型以及EV增强型的多域名SSL证…...

Docker:docker exec命令简介

介绍 docker exec [OPTIONS] 容器名称 COMMAND [ARG...] OPTIONS说明&#xff1a; -d&#xff0c;以后台方式执行命令&#xff1b; -e&#xff0c;设置环境变量 -i&#xff0c;交互模式 -t&#xff0c;设置TTY -u&#xff0c;用户名或UID&#xff0c;例如myuser:myu…...

【大数据进阶第三阶段之Hive学习笔记】Hive的数据类型与数据操作

目录 1、Hive数据类型 1.1、基本数据类型 1.2、集合数据类型 1.3、类型转化 2、DDL数据定义 2.1、创建数据库 2.2、查询数据库 2.3删除数据库 2.4、创建表 2.4.1、内部表 2.4.2、外部表 2.4.3管理表与外部表的互相转换 2.5、分区表&#xff08;partition&#xff…...

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

网络六边形受到攻击

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 抽象 现代智能交通系统 &#xff08;ITS&#xff09; 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 &#xff08;…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

HTML前端开发:JavaScript 常用事件详解

作为前端开发的核心&#xff0c;JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例&#xff1a; 1. onclick - 点击事件 当元素被单击时触发&#xff08;左键点击&#xff09; button.onclick function() {alert("按钮被点击了&#xff01;&…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

重启Eureka集群中的节点,对已经注册的服务有什么影响

先看答案&#xff0c;如果正确地操作&#xff0c;重启Eureka集群中的节点&#xff0c;对已经注册的服务影响非常小&#xff0c;甚至可以做到无感知。 但如果操作不当&#xff0c;可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别

【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而&#xff0c;传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案&#xff0c;能够实现大范围覆盖并远程采集数据。尽管具备这些优势&#xf…...

CSS | transition 和 transform的用处和区别

省流总结&#xff1a; transform用于变换/变形&#xff0c;transition是动画控制器 transform 用来对元素进行变形&#xff0c;常见的操作如下&#xff0c;它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...

【 java 虚拟机知识 第一篇 】

目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...

嵌入式常见 CPU 架构

架构类型架构厂商芯片厂商典型芯片特点与应用场景PICRISC (8/16 位)MicrochipMicrochipPIC16F877A、PIC18F4550简化指令集&#xff0c;单周期执行&#xff1b;低功耗、CIP 独立外设&#xff1b;用于家电、小电机控制、安防面板等嵌入式场景8051CISC (8 位)Intel&#xff08;原始…...