当前位置: 首页 > 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-…...

Linux应用开发之网络套接字编程(实例篇)

服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

synchronized 学习

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

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

【Elasticsearch】Elasticsearch 在大数据生态圈的地位 实践经验

Elasticsearch 在大数据生态圈的地位 & 实践经验 1.Elasticsearch 的优势1.1 Elasticsearch 解决的核心问题1.1.1 传统方案的短板1.1.2 Elasticsearch 的解决方案 1.2 与大数据组件的对比优势1.3 关键优势技术支撑1.4 Elasticsearch 的竞品1.4.1 全文搜索领域1.4.2 日志分析…...

6个月Python学习计划 Day 16 - 面向对象编程(OOP)基础

第三周 Day 3 &#x1f3af; 今日目标 理解类&#xff08;class&#xff09;和对象&#xff08;object&#xff09;的关系学会定义类的属性、方法和构造函数&#xff08;init&#xff09;掌握对象的创建与使用初识封装、继承和多态的基本概念&#xff08;预告&#xff09; &a…...

软件工程 期末复习

瀑布模型&#xff1a;计划 螺旋模型&#xff1a;风险低 原型模型: 用户反馈 喷泉模型:代码复用 高内聚 低耦合&#xff1a;模块内部功能紧密 模块之间依赖程度小 高内聚&#xff1a;指的是一个模块内部的功能应该紧密相关。换句话说&#xff0c;一个模块应当只实现单一的功能…...