当前位置: 首页 > 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;并提供了一个即时可用的…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...

HTML前端开发:JavaScript 常用事件详解

作为前端开发的核心&#xff0c;JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例&#xff1a; 1. onclick - 点击事件 当元素被单击时触发&#xff08;左键点击&#xff09; button.onclick function() {alert("按钮被点击了&#xff01;&…...

Spring AI与Spring Modulith核心技术解析

Spring AI核心架构解析 Spring AI&#xff08;https://spring.io/projects/spring-ai&#xff09;作为Spring生态中的AI集成框架&#xff0c;其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似&#xff0c;但特别为多语…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;SCL 立刻变&#…...