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

LCR 023. 相交链表

一.题目:

LCR 023. 相交链表 - 力扣(LeetCode)

二.我的原始解法-无:

三.其他人的正确及好的解法,力扣解法参考:

哈希表法及双指针法:LCR 023. 相交链表 - 力扣(LeetCode)

B站动态讲解双指针处理相交链表过程:算法动画题解:leetcode.160.相交链表(双指针)_哔哩哔哩_bilibili

四.对于别人解法的消化及总结:

首先要稍微回顾下python实现链表的方法,题目中已经给出如下链表类型定义,初始化函数中有数值部分和指针部分,然后又给出了要实现

算法的函数入参,两个链表的头结点headA和headB

# Definition for singly-linked list.

# class ListNode:

#     def __init__(self, x):

#         self.val = x

#         self.next = None

def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:

【哈希表法】就是判断两个链表的指针地址相同,说明两个链表指向了同一个节点,这样就找到了交叉节点,但是要注意实现方法和列表查询的不同,

列表查询用index简单遍历或者内置函数操作即可,链表查询要注意指针问题。判断两个链表的指针相同,可以用哈希表法,就是把一个链表的已

遍历节点放到一个哈希表中,然后使用哈希表查找时间复杂度为O(1)的特点,直接用另一个链表的每个节点在哈希表中匹配,匹配一致的返回即可,

这种方法的时间复杂度为O(m+n),就是两个链表都要遍历一次,第一次生成哈希表,第二次查找哈希表,相当于用哈希表比对两个链表。有了这种解法,

自然会想到直接比较两个链表,不用哈希表做中间过渡,就是双指针法,先实现哈希表法如下:

【双指针法】

这个算法理解起来复杂的地方在于,一个链表会遍历多次,很难分析清楚,即使给出了答案还是不相信哈哈。可以看看上面的B站视频自己画图分析下:

A,B指针开始同步走,A链条长,B链条短,假设A相交前长度x,每个节点标号1-6,B相交前长度y,相交前节点标号7。因为B链条短,所以B走了y+z后到

终点了,此时A还在x上走,此时它俩走过的路径长度相同,因为同步走。此时B跳到链表A起点并且比A落后了A走过的节点,假设是u,然后A到达终点的时候

,B走过了x+z-u个节点,此时A跳到链表B起点,当A到达交叉点时A走过了x+z+y个节点,B走过了y+z+x个节点,两者相等又是同步走的,所以二者会相遇。

编程技巧:

1.python的哈希表是用字典代替的,这道题的哈希表解法也考察了python字典的初始化、赋值、查询,分别如下:

类似列表的创建方法:s={}

赋值:s[key]=value

查询:s.get(key)

2.遍历链表直接用while p: p=p.next即可,如果直接用头指针遍历,就用头指针替代p即可,如果链表节点数>=0,while循环执行次数>=0

相关文章:

LCR 023. 相交链表

一.题目: LCR 023. 相交链表 - 力扣(LeetCode) 二.我的原始解法-无: 三.其他人的正确及好的解法,力扣解法参考: 哈希表法及双指针法:LCR 023. 相交链表 - 力扣(LeetCode&#xff0…...

Linux命令行下载工具

1. curl 1.1. 介绍 curl是一个功能强大的命令行工具,用于在各种网络协议下传输数据。它支持多种协议,包括但不限于 HTTP、HTTPS、FTP、FTPS、SCP、SFTP、SMTP、POP3、IMAP 等,这使得它在网络数据交互场景中有广泛的应用。curl可以模拟浏览器…...

期末复习-Hadoop名词解释+简答题纯享版

目录 一、名称解释(8选5) 1.什么是大数据 2.大数据的5V特征 3.什么是SSH 4.HDFS(p32) 5.名称节点 6.数据节点 7.元数据 8.倒排索引 9.单点故障 10.高可用 11.数据仓库 二、简答题 1.简述Hadoop的优点及其含义 2.简述…...

嵌入式Linux无窗口系统下搭建 Qt 开发环境

嵌入式Linux无窗口系统下搭建 Qt 开发环境 本文将介绍如何在树莓派的嵌入式 Linux 环境下,搭建 Qt 开发环境,实现无窗口系统模式(framebuffer)下的图形程序开发。 1. 安装 Qt 环境 接下来,安装核心 Qt 开发库以及与 …...

C#基础教程

1. C# 基础语法和操作符 C# 中的运算符优先级 namespace OperatorsAppl {class Program7{static void Main(string[] args){int a 20; // 定义变量aint b 10; // 定义变量bint c 15; // 定义变量cint d 5; // 定义变量dint e; // 定义变量e// 演示运算符优先级&…...

Alibaba EasyExcel 导入导出全家桶

一、阿里巴巴EasyExcel的优势 首先说下EasyExcel相对 Apache poi的优势: EasyExcel也是阿里研发在poi基础上做了封装,改进产物。它替开发者做了注解列表解析,表格填充等一系列代码编写工作,并将此抽象成通用和可扩展的框架。相对p…...

Spring Cloud + MyBatis Plus + GraphQL 完整示例

Spring Cloud MyBatis Plus GraphQL 完整示例 1、创建Spring Boot子项目1.1 配置POM,添加必要的依赖1.2 配置MyBatis-Plus 2、集成GraphQL2.1 定义schema.graphqls2.2 添加GraphQL解析器2.3 配置schame文件配置 3、访问测试3.1 查询测试(演示&#xff…...

uni-app简洁的移动端登录注册界面

非常简洁的登录、注册界面模板&#xff0c;使用uni-app编写&#xff0c;直接复制粘贴即可&#xff0c;无任何引用&#xff0c;全部公开。 废话不多说&#xff0c;代码如下&#xff1a; login.vue文件 <template><view class"content"><view class&quo…...

LongVU:用于长视频语言理解的空间时间自适应压缩

晚上闲暇时间看到一种用于长视频语言理解的空间时间自适应压缩机制的研究工作LongVU&#xff0c;主要内容包括&#xff1a; 背景与挑战&#xff1a;多模态大语言模型&#xff08;MLLMs&#xff09;在视频理解和分析方面取得了进展&#xff0c;但处理长视频仍受限于LLM的上下文长…...

Elasticsearch数据迁移(快照)

1. 数据条件 一台原始es服务器&#xff08;192.168.xx.xx&#xff09;&#xff0c;数据迁移后的目标服务器&#xff08;10.2.xx.xx&#xff09;。 2台服务器所处环境&#xff1a; centos7操作系统&#xff0c; elasticsearch-7.3.0。 2. 为原始es服务器数据创建快照 修改elas…...

Linux Cgroup学习笔记

文章目录 Cgroup(Control Group)引言简介Cgroup v1通用接口文件blkio子系统cpu子系统cpuacct子系统cpuset子系统devices子系统freezer子系统hugetlb子系统memory子系统net_cls子系统net_prio子系统perf_event子系统pids子系统misc子系统 Cgroup V2基础操作组织进程和线程popula…...

百问FB显示开发图像处理 - PNG图像处理

2.3 PNG图像处理 2.3.1 PNG文件格式和libpng编译 ​ 跟JPEG文件格式一样&#xff0c;PNG也是一种使用了算法压缩后的图像格式&#xff0c;与JPEG不同&#xff0c;PNG使用从LZ77派生的无损数据压缩算法。对于PNG文件格式&#xff0c;也有相应的开源工具libpng。 libpng库可从…...

【JavaWeb后端学习笔记】MySQL多表查询(内连接、外连接、子查询)

MySQL 多表查询 1、连接查询1.1 内连接1.2 外连接 2、子查询2.1 标量子查询2.2 列子查询2.3 行子查询2.4 表子查询 3、多表查询案例 多表查询有两大类&#xff1a;连接查询和子查询。 连接查询又分为隐式/显式内连接和左/右外连接。 子查询又分为标量子查询、列子查询、行子查询…...

RocketMQ 过滤消息 基于tag过滤和SQL过滤

RocketMQ 过滤消息分为两种&#xff0c;一种tag过滤&#xff0c;另外一种是复杂的sql过滤。 tag过滤 首先创建producer然后启动&#xff0c;在这里创建了字符串的数组tags。字符串数组里面放置了多个字符串&#xff0c;然后去发送15条消息。 15条消息随着i的增长&#xff0c;…...

element-ui 基本样式的一些更改【持续更新】

1、 去除el-tabs的底部灰色横线 ::v-deep .el-tabs__nav-wrap::after {height: 0px;}2、el-table设置表头颜色 <el-table:data"tableData":header-cell-style"{background:#F7F8FA,color:#4E5869}"><el-table-columnlabel"序号"type&qu…...

element-ui radio和checkbox禁用时不置灰还是原来不禁用时的样式

把要紧用的内容加上一个class"notEdit-page" z注意要在style里面写不能加上scoped /*//checkBox自定义禁用样式*//*//checkBox自定义禁用样式*/ .notEdit-page.el-checkbox__input.is-disabled.is-checked.el-checkbox__inner::after {border-color: #fff; } .notEdi…...

第一部分:基础知识 6. 函数 --[MySQL轻松入门教程]

MySQL 提供了丰富的内置函数&#xff0c;涵盖了字符串处理、数值计算、日期时间操作、聚合分析以及控制流等多个方面。这些函数可以帮助用户更高效地进行数据查询和处理。 1.字符串函数 MySQL 提供了丰富的字符串函数来帮助用户处理和操作字符串数据。下面是一些常用的 MySQL…...

【蓝桥杯每日一题】扫雷

扫雷 知识点 2024-12-3 蓝桥杯每日一题 扫雷 dfs &#xff08;bfs也是可行的&#xff09; 题目大意 在一个二维平面上放置这N个炸雷&#xff0c;每个炸雷的信息有$(x_i,y_i,r_i) $&#xff0c;前两个是坐标信息&#xff0c;第三个是爆炸半径。然后会输入M个排雷火箭&#xff0…...

【算法】棋盘覆盖问题源代码及精简版

目录 一、题目 二、样例 三、示例代码 四、精简代码 五、总结 对于棋盘覆盖问题的解答和优化。 一、题目 输入格式&#xff1a; 第一行&#xff0c;一个整数n&#xff08;棋盘n*n&#xff0c;n确保是2的幂次&#xff0c;n<64&#xff09; 第二行&#xff0c;两个整数…...

Django的介绍

Django是一个高级的Python Web框架&#xff0c;它鼓励快速开发和干净、实用的设计。Django遵循MVC设计模式&#xff0c;即模型&#xff08;Model&#xff09;、视图&#xff08;View&#xff09;和控制器&#xff08;Controller&#xff09;&#xff0c;并提供了一个即时可用的…...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

使用分级同态加密防御梯度泄漏

抽象 联邦学习 &#xff08;FL&#xff09; 支持跨分布式客户端进行协作模型训练&#xff0c;而无需共享原始数据&#xff0c;这使其成为在互联和自动驾驶汽车 &#xff08;CAV&#xff09; 等领域保护隐私的机器学习的一种很有前途的方法。然而&#xff0c;最近的研究表明&…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

Cinnamon修改面板小工具图标

Cinnamon开始菜单-CSDN博客 设置模块都是做好的&#xff0c;比GNOME简单得多&#xff01; 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

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; …...