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

【C++刷题】力扣-#594-最长和谐子序列

题目描述

和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。
给你一个整数数组 nums ,请你在所有可能的子序列中找到最长的和谐子序列的长度。 数组的 子序列是一个由数组派生出来的序列,它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。

示例

示例 1

输入:nums = [1,3,2,2,5,2,3,7]
输出:5
解释:
最长和谐子序列是 [3,2,2,2,3]

示例 2

输入:nums = [1,2,3,4]
输出:2
解释:
最长和谐子序列是 [1,2][2,3][3,4],长度都为 2

示例 3

输入:nums = [1,1,1,1]
输出:0
解释:
不存在和谐子序列。

题解

  1. 统计每个数字的出现次数:使用哈希表 countMap 来统计 nums 中每个数字的出现次数。
  2. 寻找和谐子序列:遍历哈希表中的每个数字,对于每个数字 num,检查 num + 1 是否也存在于哈希表中。如果存在,则说明找到了一个长度至少为2的和谐子序列。将这两个数字的出现次数相加,得到这个子序列的长度,并更新最长和谐子序列的长度。
  3. 返回结果:返回计算出的最长和谐子序列的长度。

代码实现

int findLHS(vector<int>& nums) {unordered_map<int, int> countMap;unordered_set<int> numSet;// 统计每个数字的出现次数并存储在集合中for (int num : nums) {countMap[num]++;numSet.insert(num);}int maxLength = 0;// 遍历集合中的数字,找到最大值和最小值相差为1的两个值for (int num : numSet) {if (numSet.find(num + 1) != numSet.end()) {// 计算子序列的长度int length = countMap[num] + countMap[num + 1];maxLength = max(maxLength, length);}}return maxLength;
}

复杂度分析

● 时间复杂度:O(n),其中 n 是数组 nums 的长度。我们需要遍历一次数组来构建哈希表和集合,然后遍历集合中的每个元素来计算子序列的长度。
● 空间复杂度:O(n),用于存储哈希表和集合。
这个算法的优势在于它直接使用哈希表来统计数字的出现次数,并通过一次遍历来找到最长和谐子序列的长度。这种方法简单且高效,适用于处理大数据集。

相关文章:

【C++刷题】力扣-#594-最长和谐子序列

题目描述 和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。 给你一个整数数组 nums &#xff0c;请你在所有可能的子序列中找到最长的和谐子序列的长度。 数组的 子序列是一个由数组派生出来的序列&#xff0c;它可以通过删除一些元素或不删除元素、且不改变…...

MoveIt 控制自己的真实机械臂【2】——编写 action server 端代码

完成了 MoveIt 这边 action client 的基本配置&#xff0c;MoveIt 理论上可以将规划好的 trajectory 以 action 的形式发布出来了&#xff0c;浅浅尝试一下&#xff0c;在 terminal 中运行 roslaunch xmate7_moveit_config_new demo.launch 报错提示他在等待 xmate_arm_control…...

C#制作学生管理系统

定义学生类 定义一个简单的类来表示学生&#xff0c;包括学号、姓名、性别、年龄、电话、地址。再给其添加一个方法利于后续添加方法查看学生信息。 //定义学生类 public class student {public int ID { get; set; }//开放读写权限public string Name { get; set; }public i…...

python Pandas合并(单元格、sheet、excel )

安装 Pandas 和 openpyxl 首先&#xff0c;确保已经安装了 Pandas 和 openpyxl。可以通过 pip 安装&#xff1a; pip install pandas openpyxl 创建 DataFrame import pandas as pd # 创建 DataFrame df1 pd.DataFrame({ 姓名: [张三, 李四, 王五], 年龄: [25, 30, 35]…...

OJ在线编程常见输入输出练习【JavaScript】

&#xff08;注&#xff1a;本文是对【JavaScript Node 】 ACM模式&#xff0c;常见输入输出练习相关内容的介绍&#xff01;&#xff01;&#xff01;&#xff09; 牛客竞赛_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ 一、ACM模式下的编辑页面 二、ACM模式下&a…...

新能源汽车空调系统:绿色出行的舒适保障

在新能源汽车迅速发展的今天&#xff0c;空调系统作为提升驾乘舒适度的重要组成部分&#xff0c;发挥着不可或缺的作用。新能源汽车空调系统主要由压缩机、冷凝器、节流装置和蒸发器四大件组成&#xff0c;它们协同工作&#xff0c;为车内提供适宜的温度和湿度环境。 一、压缩…...

Date工具类详细汇总-Date日期相关方法

# 1024程序员节 | 征文 # 目录 简介 Date工具类单元测试 Date工具类 简介 本文章是个人总结实际工作中常用到的Date工具类&#xff0c;主要包含Java-jdk8以下版本的Date相关使用方法&#xff0c;可以方便的在工作中灵活的应用&#xff0c;在个人工作期间频繁使用这些时间的格…...

TMUX1308PWR规格书 数据手册 具有注入电流控制功能的 5V 双向 8:1单通道和 4:1 双通道多路复用器芯片

TMUX1308 和 TMUX1309 为通用互补金属氧化物半导体 (CMOS) 多路复用器 (MUX)。TMUX1308 是 8:1单通道&#xff08;单端&#xff09;多路复用器&#xff0c;而 TMUX1309 是 4:1 双通道&#xff08;差分&#xff09;多路复用器。这些器件可在源极 (Sx) 和漏极 (Dx) 引脚上支持从 …...

证件照怎么换底色?简单又快速!不看后悔

一、引言 证件照在我们的生活中有着广泛的应用&#xff0c;无论是求职、考试还是办理各种证件&#xff0c;都需要用到不同底色的证件照。传统的换底色方法往往比较复杂&#xff0c;需要一定的专业技能和软件操作经验。但是现在&#xff0c;有了更简单快捷的方法&#xff0c;让你…...

Rust 基础语法与常用特性

Rust 跨界&#xff1a;全面掌握跨平台应用开发 第一章&#xff1a;快速上手 Rust 1.2 基础语法与常用特性 1.2.1 数据类型与控制流 数据类型 Rust 提供了丰富的内置数据类型&#xff0c;主要分为标量类型和复合类型。 标量类型 标量类型表示单一的值&#xff0c;Rust 中…...

一、开发环境的搭建

环境搭建步骤&#xff1a; 下载软件安装软件运行软件 其他&#xff1a; Visual studio 安装包文件&#xff1a;https://www.alipan.com/s/nd5RgzD4e3b 下载软件 在浏览器中搜索Visual studio&#xff0c;选择如图的选项 点击该区域&#xff0c;进入该页面&#xff0c;【或…...

Docker:存储原理

Docker&#xff1a;存储原理 镜像联合文件系统overlay镜像存储结构容器存储结构 存储卷绑定挂载存储卷结构 镜像 联合文件系统 联合文件系统Union File System是一种分层&#xff0c;轻量且高效的文件系统。其将整个文件系统分为多个层&#xff0c;层与层之间进行覆盖&#x…...

ts:数组的常用方法(push、pop、shift、unshift、splice、slice)

前端css中filter的使用 一、主要内容说明二、例子&#xff08;一&#xff09;、push方法&#xff08;尾添加&#xff09;1.源码1 &#xff08;push方法&#xff09;2.源码1运行效果 &#xff08;二&#xff09;、pop方法&#xff08;尾删除&#xff09;1.源码2&#xff08;pop方…...

物联网网关确保设备安全

物联网&#xff08;IoT&#xff09;网关在确保设备安全方面扮演着至关重要的角色。 作为连接物联网设备和云端或企业系统的中介&#xff0c;物联网网关可以实施多种安全措施来保护设备和数据。 是物联网网关确保设备安全的关键方法&#xff1a; 1. 设备认证和授权 认证&…...

Vue学习笔记(五)

Class绑定 数据绑定的一个常见需求场景式操纵元素的CSS class列表&#xff0c;因为class是attribute,我们可以和其他attribute一样使用v-bind将它们和动态的字符串绑定。但是&#xff0c;在处理比较复杂的绑定时&#xff0c;通过拼接生成字符串是麻烦且易出错的。因此&#xf…...

Nestjs返回格式小结

在 NestJS 中&#xff0c;除了 text/event-stream&#xff08;用于 Server-Sent Events&#xff09;之外&#xff0c;还有多种格式的返回方式&#xff0c;具体取决于你的应用需求。以下是一些常见的返回格式及其示例&#xff1a; 1. JSON 格式 Get(json) getJsonResponse(Res…...

【力扣刷题实战】相同的树

大家好&#xff0c;我是小卡皮巴拉 文章目录 目录 力扣题目&#xff1a; 相同的树 题目描述 示例 1&#xff1a; 示例 2&#xff1a; 示例 3&#xff1a; 解题思路 题目理解 算法选择 具体思路 解题要点 完整代码&#xff08;C语言&#xff09; 兄弟们共勉 &#…...

Golang | Leetcode Golang题解之第515题在每个树行中找最大值

题目&#xff1a; 题解&#xff1a; func largestValues(root *TreeNode) (ans []int) {if root nil {return}q : []*TreeNode{root}for len(q) > 0 {maxVal : math.MinInt32tmp : qq nilfor _, node : range tmp {maxVal max(maxVal, node.Val)if node.Left ! nil {q …...

Zookeeper 对于 Kafka 的作用是什么?

大家好&#xff0c;我是锋哥。今天分享关于【Zookeeper 对于 Kafka 的作用是什么&#xff1f;】面试题&#xff1f;希望对大家有帮助&#xff1b; Zookeeper 对于 Kafka 的作用是什么&#xff1f; 1000道 互联网大厂Java工程师 精选面试题-Java资源分享网 ZooKeeper 在 Kafka…...

Thread类及线程的核心操作

一. Thread类的常见构造方法 1. Thread() Thread类无参的构造方法, 用于创建Thread类的实例对象. 2. Thread(String name) 带一个参数的Thread类构造方法, 创建一个线程对象, 并给其命名. [注]: 如果不专门给线程命名, 那么线程默认的名字就是Thread-0, Thread-1, Thread-…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

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

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

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现

摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序&#xff0c;以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务&#xff0c;提供稳定高效的数据处理与业务逻辑支持&#xff1b;利用 uniapp 实现跨平台前…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/

使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题&#xff1a;docker pull 失败 网络不同&#xff0c;需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...