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

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

React 第五十五节 Router 中 useAsyncError的使用详解

前言 useAsyncError 是 React Router v6.4 引入的一个钩子&#xff0c;用于处理异步操作&#xff08;如数据加载&#xff09;中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误&#xff1a;捕获在 loader 或 action 中发生的异步错误替…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

练习(含atoi的模拟实现,自定义类型等练习)

一、结构体大小的计算及位段 &#xff08;结构体大小计算及位段 详解请看&#xff1a;自定义类型&#xff1a;结构体进阶-CSDN博客&#xff09; 1.在32位系统环境&#xff0c;编译选项为4字节对齐&#xff0c;那么sizeof(A)和sizeof(B)是多少&#xff1f; #pragma pack(4)st…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

2024年赣州旅游投资集团社会招聘笔试真

2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

QT: `long long` 类型转换为 `QString` 2025.6.5

在 Qt 中&#xff0c;将 long long 类型转换为 QString 可以通过以下两种常用方法实现&#xff1a; 方法 1&#xff1a;使用 QString::number() 直接调用 QString 的静态方法 number()&#xff0c;将数值转换为字符串&#xff1a; long long value 1234567890123456789LL; …...