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

力扣hot3--并查集+哈希

第一想法是排个序然后遍历一遍,but时间复杂度就超啦

并查集居然与哈希结合了()

已经好久没用过并查集了,,,我们用哈希表f_node中来记录原结点的父节点,其中key是原结点,value是父节点。我们用哈希表cnt来记录原结点所在集合的元素数目(只有这一集合的父节点的cnt才有效,即我们只维护父节点cnt的正确性),其中key是原结点,value是集合中元素的数目。

用哈希表来记录的好处是可以直接用.count()来查看是否存在临近元素:我们遍历nums中的每一个元素,依次判断元素值-1和元素值+1是否存在于某个集合中,如果存在,那就和元素值所在的集合合并。用res来维护最终结果。

class Solution {
public:int res=1;unordered_map<int,int> f_node;unordered_map<int,int> cnt;int find(int x){if(f_node[x]==x){return x;}f_node[x]=find(f_node[x]);return f_node[x];}void union_xy(int x,int y){int f_x=find(x);int f_y=find(y);if(f_x==f_y){return ;}f_node[f_x]=f_y;cnt[f_y]+=cnt[f_x];res=max(res,cnt[f_y]);}int longestConsecutive(vector<int>& nums) {if(nums.size()==0){return 0;}for(auto i:nums){f_node[i]=i;cnt[i]=1;}for(auto i:nums){if(f_node.count(i-1)){union_xy(i-1,i);}if(f_node.count(i+1)){union_xy(i,i+1);}}return res;}
};

简单注意一下:i 分别是nums中的数值

for(auto i:nums){if(f_node.count(i-1)){union_xy(i-1,i);}if(f_node.count(i+1)){union_xy(i,i+1);}
}

python3版本:

class Solution:res=1f_node={}cnt={}def find(self,x):if self.f_node[x]==x:return xself.f_node[x]=self.find(self.f_node[x])return self.f_node[x]def union_xy(self,x,y):f_x=self.find(x)f_y=self.find(y)if f_x==f_y:returnself.f_node[f_x]=f_yself.cnt[f_y]+=self.cnt[f_x]self.res=max(self.res,self.cnt[f_y])def longestConsecutive(self, nums: List[int]) -> int:self.res=1self.f_node={}self.cnt={}if len(nums)==0:return 0for i in nums:self.f_node[i]=iself.cnt[i]=1for i in nums:if i-1 in self.f_node:self.union_xy(i-1,i)if i+1 in self.f_node:self.union_xy(i,i+1)return self.res

看某个元素是否在列表中:直接用 in , 判断一个列表用 len() 即可

相关文章:

力扣hot3--并查集+哈希

第一想法是排个序然后遍历一遍&#xff0c;but时间复杂度就超啦 并查集居然与哈希结合了&#xff08;&#xff09; 已经好久没用过并查集了&#xff0c;&#xff0c;&#xff0c;我们用哈希表f_node中来记录原结点的父节点&#xff0c;其中key是原结点&#xff0c;value是父节点…...

微信网页版能够使用(会顶掉微信app的登陆)

一、文件结构 新建目录chrome新建icons&#xff0c;其中图片你自己找吧新建文件manifest.json新建文件wx-rules.json 二、文件内容 对应的png你们自己改下 1、manifest.json {"manifest_version": 3,"name": "wechat-need-web","author…...

word软件中硬件图像加速有什么用处?禁用硬件图形加速(G)会影响word文档中插入图片的分辨率吗?

问题描述&#xff1a;word软件中硬件图像加速有什么用处&#xff1f;禁用硬件图形加速(G)会影响word文档中插入图片的分辨率吗&#xff1f; 问题解答&#xff1a; 在 Microsoft Word 中&#xff0c;硬件图形加速主要用于提高图形元素的渲染速度和性能&#xff0c;特别是处理大…...

.NET Core MongoDB数据仓储和工作单元模式封装

前言 上一章我们把系统所需要的MongoDB集合设计好了&#xff0c;这一章我们的主要任务是使用.NET Core应用程序连接MongoDB并且封装MongoDB数据仓储和工作单元模式&#xff0c;因为本章内容涵盖的有点多关于仓储和工作单元的使用就放到下一章节中讲解了。仓储模式&#xff08;R…...

lua:有关表访问的metamethod

针对在两种正常状态&#xff1a;表的不存在的域的查询和修改&#xff0c;Lua也提供了改变 tables的行为的方法。 index metamethod 我们可以通过index元方法来实现访问table内部不存在的域时人为操控返回数据。 比如以下测试代码&#xff1a; local set {1,2,3} setmetata…...

【MySQL】索引事务

MySQL索引事务 1. 索引1.1 概念1.2 作用1.3 使用场景1.4 使用1.5 案例 2. 事务2.2 事物的概念2.3 使用 3. 内容重点总结 1. 索引 1.1 概念 索引是一种特殊的文件&#xff0c;包含着对数据表里所有记录的引用指针。可以对表中的一列或多列创建索引&#xff0c; 并指定索引的类…...

ChatGPT重大升级:能自动记住用户的习惯和喜好,用户有权决定是否共享数据给OpenAI

OpenAI刚刚宣布了ChatGPT的一项激动人心的更新&#xff01; OpenAI在ChatGPT中新加了记忆功能和用户控制选项&#xff0c;这意味着GPT能够在与用户的互动中记住之前的对话内容&#xff0c;并利用这些信息在后续的交谈中提供更加相关和定制化的回答。 这一功能目前正处于测试阶…...

CSS设置盒子阴影

语法 box-shadow: *h-shadow v-shadow blur spread color* inset; 注释: box-shadow向框添加一个或多个阴影. 该属性是由逗号分隔的阴影列表,每个阴影由2-4个长度值、可选的颜色值及可选的inset关键词来规定。省略长度的值是0。 外阴影 a、给元素右边框和下边框加外阴影——把…...

文件夹删不掉,显示在另一个文件中打开怎么办

问题&#xff1a; 一、想要删掉这个文件夹&#xff0c;却因为文件夹中的文件打开了删不掉&#xff0c;这里我因为做的测试&#xff0c;所以是知道打开了什么 二、一般情况下文件比较多时&#xff0c;是不知道打开了什么的&#xff0c;长这个样子 解决&#xff1a; 一、打开任…...

阿里云香港云服务器租用_BGP多线网络_CN2高速线路测试

阿里云香港服务器中国香港数据中心网络线路类型BGP多线精品&#xff0c;中国电信CN2高速网络高质量、大规格BGP带宽&#xff0c;运营商精品公网直连中国内地&#xff0c;时延更低&#xff0c;优化海外回中国内地流量的公网线路&#xff0c;可以提高国际业务访问质量。阿里云服务…...

C# 异步方法的使用场景

我一直认为C#的异步方法只是一堆华而不实的东西&#xff0c;坑特别多&#xff0c;比起直接自建线程也没有任何优势。 直到有一天&#xff0c;一个需求场景&#xff0c;让我再次想到了C#的异步方法。 需求场景如下&#xff1a;需要写一个程序控制机械臂完成各种动作。每个动作要…...

Lua 教程

Lua 教程 (今天又又又开新坑啦) Lua 教程 手册简介 Lua 是一种轻量小巧的脚本语言&#xff0c;用标准C语言编写并以源代码形式开放。 手册说明 Lua是什么? Lua 是一个小巧的脚本语言。是巴西里约热内卢天主教大学&#xff08;Pontifical Catholic University of Rio de …...

CleanMyMac X2024版本有哪些常见的使用场景?

CleanMyMac X作为一款Mac电脑清理和优化工具&#xff0c;具有多种使用场景。以下是一些常见的使用场景&#xff1a; 清理系统垃圾文件&#xff1a;CleanMyMac X可以智能扫描Mac磁盘空间&#xff0c;清理系统冗余文件和各种软件应用产生的垃圾文件&#xff0c;如缓存、日志文件…...

《Docker快速入门:从0到1构建你的第一个容器!》

《Docker快速入门&#xff1a;从0到1构建你的第一个容器&#xff01;》 前言 欢迎来到Docker的世界&#xff0c;一个让应用程序打包、部署和运行更加容易的神奇平台。Docker改变了我们对于应用开发和分发的看法&#xff0c;它通过容器技术让软件的携带和运行变得前所未有的轻…...

NLP_Transformer架构

文章目录 Transformer架构剖析编码器-解码器架构各种注意力的应用Transformer中的自注意力Transformer中的多头自注意力Transformer中的编码器-解码器注意力Transformer中的注意力掩码和因果注意力 编码器的输入和位置编码编码器的内部结构编码器的输出和编码器-解码器的连接解…...

CVE-2012-2311 漏洞复现

CVE-2012-2311 这个漏洞被爆出来以后&#xff0c;PHP官方对其进行了修补&#xff0c;发布了新版本5.4.2及5.3.12&#xff0c;但这个修复是不完全的&#xff0c;可以被绕过&#xff0c;进而衍生出CVE-2012-2311漏洞。 PHP的修复方法是对-进行了检查&#xff1a; if(query_str…...

多线程面试题汇总

多线程面试题汇总 一、多线程1、线程的生命周期2、线程的创建&#xff08;函数创建&#xff09;3、线程的创建&#xff08;使用类&#xff09;4、守护线程 二、全局解释器锁1、使用单线程实现累加到5000000002、使用多线程实现累加到5000000003、总结 三、线程安全1、多线程之数…...

CentOS7.9+Kubernetes1.29.2+Docker25.0.3高可用集群二进制部署

CentOS7.9Kubernetes1.29.2Docker25.0.3高可用集群二进制部署 Kubernetes高可用集群&#xff08;Kubernetes1.29.2Docker25.0.3&#xff09;二进制部署二进制软件部署flannel v0.22.3网络&#xff0c;使用的etcd是版本3&#xff0c;与之前使用版本2不同。查看官方文档进行了解…...

STM32——OLED菜单(二级菜单)

文章目录 一.补充二. 二级菜单代码 简介&#xff1a;首先在我的51 I2C里面有OLED详细讲解&#xff0c;本期代码从51OLED基础上移植过来的&#xff0c;可以先看完那篇文章&#xff0c;在看这个&#xff0c;然后按键我是用的定时器扫描不会堵塞程序,可以翻开我的文章有单独的定时…...

配置Vite+React+TS项目

初始化 执行npm create vite并填写项目名、用那个框架。。 配置 路径别名 在vite.config.ts里面配置&#xff1a; import { defineConfig } from vite import react from vitejs/plugin-react import path from pathexport default defineConfig({plugins: [react()],reso…...

Vue记事本应用实现教程

文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展&#xff1a;显示创建时间8. 功能扩展&#xff1a;记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

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

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

MongoDB学习和应用(高效的非关系型数据库)

一丶 MongoDB简介 对于社交类软件的功能&#xff0c;我们需要对它的功能特点进行分析&#xff1a; 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具&#xff1a; mysql&#xff1a;关系型数据库&am…...

FFmpeg 低延迟同屏方案

引言 在实时互动需求激增的当下&#xff0c;无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作&#xff0c;还是游戏直播的画面实时传输&#xff0c;低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架&#xff0c;凭借其灵活的编解码、数据…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

定时器任务——若依源码分析

分析util包下面的工具类schedule utils&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 JobD…...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

AspectJ 在 Android 中的完整使用指南

一、环境配置&#xff08;Gradle 7.0 适配&#xff09; 1. 项目级 build.gradle // 注意&#xff1a;沪江插件已停更&#xff0c;推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...

LeetCode - 199. 二叉树的右视图

题目 199. 二叉树的右视图 - 力扣&#xff08;LeetCode&#xff09; 思路 右视图是指从树的右侧看&#xff0c;对于每一层&#xff0c;只能看到该层最右边的节点。实现思路是&#xff1a; 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...

网站指纹识别

网站指纹识别 网站的最基本组成&#xff1a;服务器&#xff08;操作系统&#xff09;、中间件&#xff08;web容器&#xff09;、脚本语言、数据厍 为什么要了解这些&#xff1f;举个例子&#xff1a;发现了一个文件读取漏洞&#xff0c;我们需要读/etc/passwd&#xff0c;如…...