( 哈希表) 594. 最长和谐子序列 ——【Leetcode每日一题】

❓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

示例 3:

输入:nums = [1,1,1,1]
输出:0

提示:

  • 1 < = n u m s . l e n g t h < = 2 ∗ 1 0 4 1 <= nums.length <= 2 * 10^4 1<=nums.length<=2104
  • − 1 0 9 < = n u m s [ i ] < = 1 0 9 -10^9 <= nums[i] <= 10^9 109<=nums[i]<=109

💡思路:哈希表

  1. 我们首先遍历一遍数组,用一个哈希映射来存储每个数出现的次数;
  2. 随后遍历哈希映射,设当前遍历到的键值对为 (key,value),那么我们就查询 key+1 在哈希映射中对应的统计次数,就得到了 keykey+1出现的次数,和谐子序列的长度等于 keykey+1 出现的次数之和。
  3. 求最大值。

🍁代码:(Java、C++)

Java

class Solution {
    public int findLHS(int[] nums) {
        Map<Integer, Integer> countForNum = new HashMap<>();
        for(int num : nums){
            countForNum.put(num, countForNum.getOrDefault(num, 0) + 1);
        }
        int longest = 0;
        for (int num : countForNum.keySet()) {
            if (countForNum.containsKey(num + 1)) {
                longest = Math.max(longest, countForNum.get(num + 1) + countForNum.get(num));
            }
        }
        return longest;
    }
}

C++

class Solution {
public:
    int findLHS(vector<int>& nums) {
        unordered_map<int, int> countForNum;
        for (int num : nums) {
            countForNum[num]++;
        }
        int longest = 0;
        for(auto num : countForNum){
            if(countForNum.count(num.first + 1)){
                longest = max(longest, num.second + countForNum[num.first + 1]);
            }
        }
        return longest;
    }
};

🚀 运行结果:

在这里插入图片描述

🕔 复杂度分析:

  • 时间复杂度 O ( n ) O(n) O(n),其中 n 为数组的长度。
  • 空间复杂度 O ( n ) O(n) O(n),其中 n 为数组的长度。数组中最多有 n 个不同元素,因此哈希表最多存储 n 个数据。

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我 leetCode专栏,每日更新!

注: 如有不足,欢迎指正!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/15857.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

AWSFireLens轻松实现容器日志处理

applog应用程序和fluent-bit共享磁盘&#xff0c;日志内容是json格式数据&#xff0c;输出到S3也是JSON格式 applog应用部分在applog目录&#xff1a; Dockerfile文件内容 FROM alpine RUN mkdir -p /data/logs/ COPY testlog.sh /bin/ RUN chmod 777 /bin/testlog.sh ENTRYP…

MySQL知识学习01

1、什么是关系型数据库? 顾名思义&#xff0c;关系型数据库&#xff08;RDBMS&#xff0c;Relational Database Management System&#xff09;就是一种建立在关系模型的基础上的数据库。关系模型表明了数据库中所存储的数据之间的联系&#xff08;一对一、一对多、多对多&am…

宏基因组组装 | 就现在!做出改变!!

微生态研究的核心难点是什么&#xff01; 基因组组装&#xff01; 从宏基因组数据中组装获得细菌的完整基因组&#xff08;complete MAGs&#xff09;是微生物组研究的长期目标&#xff0c;但基于NGS的宏基因组测序和组装方法是无法实现完整的细菌基因组组装的。即便是红极一…

【五一创作】Apollo(入门)

Apollo(入门) Quick Start 配置中心是一种统一管理各种应用配置的基础服务组件 Apollo&#xff08;阿波罗&#xff09;是携程框架部门研发的分布式配置中心&#xff0c;能够集中化管理应用不同环境、不同集群的配置&#xff0c;配置修改后能够实时推送到应用端&#xff0c;并且…

使用pands.rolling方法实现移动窗口的聚合计算

一个问题举例 假设有一个5天的收益数据&#xff0c;需要每3天求出一次平均值来达成某个需求&#xff1a; daterevenue2023-05-01102023-05-02202023-05-03302023-05-04402023-05-0550 1号、2号和3号的数据求一次平均值&#xff0c;2号、3号和4号的数据求一次平均值&#xff…

5.4.1树的存储结构 5.4.2树和森林的遍历

回忆一下树的逻辑结构&#xff1a; 双亲表示法&#xff08;顺序存储&#xff09; 如果增加一个结点M&#xff0c;L。毋须按照逻辑上的次序存储。 如果是删除元素&#xff1a; 方案一&#xff1a;比如说删除元素为G,设置其双亲结点为-1。 方案二&#xff1a; 把尾部的结点提上…

Sybase使用sp_helptext查看系统存储过程的源码

sp_helptext存储过程用于显示已编译对象的源代码。 sp_helptext是Sybase ASE内置的存储过程&#xff0c;可从任何位置调用。 但实际上&#xff0c;如果直接使用&#xff0c;常常会得到&#xff08;令人头大的&#xff09;错误提示&#xff1a; Msg 17461 Object does not exi…

基于JavaSpringboot+vue国风汉服文化交流宣传系统

基于JavaSpringbootvue国风汉服文化交流宣传系统 博主介绍&#xff1a;5年java开发经验&#xff0c;专注Java开发、定制、远程、指导等,csdn特邀作者、专注于Java技术领域 作者主页 超级帅帅吴 Java项目精品实战案例《500套》 欢迎点赞 收藏 ⭐留言 文末获取源码联系方式 文章目…

【可解释AI】图神经网络的可解释性方法及GNNexplainer代码示例

图神经网络的可解释性方法及GNNexplainer代码示例 GNNExplainerIntroductionModelSingle-instance explanations&#xff08;Explanation via Structural Information&#xff09;Joint learning of graph structural and node feature information&#xff08;Explanation via…

SuperMap iClient3D for Cesium 构建隧道

作者&#xff1a;kele 背景 前段时间看到一篇构建隧道的文章&#xff08;https://blog.csdn.net/supermapsupport/article/details/128453116&#xff09;&#xff0c;突然想到一个使用场景&#xff1a;隧道通常是建在山体下面&#xff0c;是否可以通过这种方式构建出一条贯穿…

使用Python和机器学习进行文本情感分类

使用Python和机器学习进行文本情感分类 1. 效果图2. 原理3. 源码参考这篇博客将介绍如何使用Python进行机器学习的文本情感分类(Text Emotions Classification)。 1. 效果图 训练文本及情感分类前5条数据如下: 训练过程及测试文本情感分类效果图如下: 可以看到 对文本“S…

【量化交易笔记】5.SMA,EMA 和WMA区别

股票中的SMA&#xff0c;EMA和WMA是常用的技术分析指标。这些指标基于历史股价计算得出&#xff0c;可以帮助投资者了解股票的趋势&#xff0c;为决策提供依据。虽然它们都是平均值算法&#xff0c;但它们之间还是有一些区别的。 SMA 简单移动平均线&#xff08;Simple Moving…

分布式的流处理平台Kafka

目录&#xff1a; 一、简介二、基本概念三、生产者使用详解四、发送消息五、消费者代码示例 一、简介 ApacheKafka 是一个分布式的流处理平台。它具有以下特点&#xff1a; 支持消息的发布和订阅&#xff0c;类似于 RabbtMQ、ActiveMQ 等消息队列&#xff1b;支持数据实时处理…

计算机组成原理第五章(2)---中断

5.1概述 产生和应用 在IO设备和主机交换数据时&#xff0c;由于设备本身的机电特性的影响&#xff0c;其工作速度比较低&#xff0c;与CPU无法匹配&#xff0c;如果采用程序查询的方式需要CPU进行等待&#xff0c;但是如果在等待的过程中CPU可以执行其他的程序&#xff0c;可…

【@Param注解】| 台面使用——>底层原理分析

🐇 🐇 😄 🐇 🐇 🐇 🐇 😄 🐇 🐇 🐇 🐇 😄 🐇 🐇 🐇 🐇 😄 🐇 🐇 🐇 🐇 😄 目录 🦁 定义🦁 台面使用🦁 底层原理分析🦁 尾声🐇 🐇 😄 🐇 🐇 🐇 🐇 😄 🐇 🐇 🐇 🐇 😄 🐇 🐇 🐇 🐇 😄…

java实现乘法的方法

我们都知道&#xff0c;乘法运算的核心思想就是两个数相乘&#xff0c;如果能将乘法运算转化成一个加数的运算&#xff0c;那么这个问题就很容易解决。比如我们要实现23的乘法&#xff0c;首先需要定义两个变量&#xff1a;2和3。我们将这两个变量定义为一个变量&#xff1a;2x…

PySide6/PyQT多线程之 信号与槽 / (Signal Slot)的高效利用

前言 PySide6/PyQT信号槽是一种事件处理方式&#xff0c;允许程序中的对象发送和接收信号。 在 PySide6/PyQT 精进的过程中&#xff0c;一定躲不开 信号和槽 这座大山&#xff0c;这是一个比较有意思的知识点&#xff1a; 初接触的看不懂&#xff0c;觉得复杂&#xff1b;看得…

本地 WAF 已死,云 WAF 永生

多年来&#xff0c;Web 应用程序防火墙 (WAF) 一直是应用程序保护的代名词。事实上&#xff0c;许多应用程序安全团队认为保护其应用程序的最佳选择是一流的本地 WAF 解决方案&#xff0c;尤其是当这些应用程序部署在本地或私有云中时。 但自从引入本地 WAF 以来&#xff0c;…

JMeter的使用(二)

九、直连数据库 通过直连数据库让程序代替接口访问数据库&#xff0c;如果二者预期结果不一致&#xff0c;就找到了程序缺陷。 获取某条学院的名字&#xff0c;放在百度搜索: JMeter 不具备直连数据库功能&#xff0c;必须整合第三方(jar包)实现配置数据库的连接通过JDBC Re…

@PostConstruct注解和@PreDestroy注解

前言 Bean注解指定初始化和销毁的方法&#xff0c;也介绍了使用InitializingBean和DisposableBean来处理bean的初始化和销毁。JDK中还提供了两个注解能够在bean创建完成并且属性赋值完成之后执行一些初始化工作和在容器销毁bean之前通知我们进行一些清理工作。 1.PostConstru…