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

[LeetBook]【学习日记】寻找链表相交节点

来源于「Krahets」的《图解算法数据结构》
https://leetcode.cn/leetbook/detail/illustration-of-algorithm/

本题与主站 160 题相同:https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

训练计划 V

某教练同时带教两位学员,分别以链表 l1、l2
记录了两套核心肌群训练计划,节点值为训练项目编号。两套计划仅有前半部分热身项目不同,后续正式训练项目相同。请设计一个程序找出并返回第一个正式训练项目编号。如果两个链表不存在相交节点,返回null 。

输入说明:
intersectVal - 相交的起始节点的值。如果不存在相交节点,这一值为 0
l1 - 第一个训练计划链表
l2 - 第二个训练计划链表
skip1 - 在 l1 中(从头节点开始)跳到交叉节点的节点数
skip2 - 在 l2 中(从头节点开始)跳到交叉节点的节点数
程序将根据这些输入创建链式数据结构,并将两个头节点 head1 和 head2
传递给你的程序。如果程序能够正确返回相交节点,那么你的解决方案将被视作正确答案 。

示例 1:
输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA
= 2, skipB = 3 输出:Reference of the node with value = 8 解释:第一个正式训练项目编号为 8 (注意,如果两个列表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为[5,0,1,8,4,5]。在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。

示例 2:
输入:intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3,
skipB = 1 输出:Reference of the node with value = 2 解释:第一个正式训练项目编号为 2
(注意,如果两个列表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [0,9,1,2,4],链表 B 为 [3,2,4]。在 A中,相交节点前有 3 个节点;在 B 中,相交节点前有 1 个节点。

示例 3:
输入:intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB
= 2 输出:null 解释:两套计划完全不同,返回 null。从各自的表头开始算起,链表 A 为 [2,6,4],链表 B 为 [1,5]。由于这两个链表不相交,所以 intersectVal 必须为 0,而 skipA 和 skipB 可以是任意值。

注意:
如果两个链表没有交点,返回 null. 在返回结果后,两个链表仍须保持原有的结构。 可假定整个链表结构中没有循环。 程序尽量满足 O(n)
时间复杂度,且仅用 O(1) 内存。 本题与主站 160题相同:https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

作者:Krahets
链接:https://leetcode.cn/leetbook/read/illustration-of-algorithm/7fvoq2/
来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

暴力解法

  1. 利用 unordered_set 这种数据结构存储 A 链表节点,由于这种结构的 find 效率很高,故可在其中直接检索是否存在 B 链表的节点,存在则为交点
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {unordered_set<ListNode *> addrOfNode;while(headA){addrOfNode.insert(headA);headA = headA->next; }while(headB){if(addrOfNode.find(headB) != addrOfNode.end()){return headB;}else{headB = headB->next;}}return nullptr;}
};

双指针解法

在这里插入图片描述

  • 设置指针 a 和 b 分别遍历两条链表后再遍历对方那一条链表,指针相遇有a+(b−c)=b+(a−c),即为交点
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode *a = headA, *b = headB;while(a != b){a = a ? a->next : headB;b = b ? b->next : headA;}return a;}
};

相关文章:

[LeetBook]【学习日记】寻找链表相交节点

来源于「Krahets」的《图解算法数据结构》 https://leetcode.cn/leetbook/detail/illustration-of-algorithm/ 本题与主站 160 题相同&#xff1a;https://leetcode-cn.com/problems/intersection-of-two-linked-lists/ 训练计划 V 某教练同时带教两位学员&#xff0c;分别以…...

【Python】OpenCV-使用ResNet50进行图像分类

使用ResNet50进行图像分类 如何使用ResNet50模型对图像进行分类。 import os import cv2 import numpy as np from tensorflow.keras.applications.resnet50 import ResNet50, preprocess_input, decode_predictions from tensorflow.keras.preprocessing import image# 设置…...

TypeError: `dumps_kwargs` keyword arguments are no longer supported

TypeError: dumps_kwargs keyword arguments are no longer supported 1. 问题描述2. 解决方法 1. 问题描述 使用 FastChat 启动私有大语言模型&#xff0c;通过一些 UI 工具进行访问时&#xff0c;报以下错误。 略 2024-02-29 09:26:14 | ERROR | stderr | yield f"…...

设计模式学习笔记 - 设计原则 - 3.里氏替换原则,它和多态的区别是什么?

前言 今天来学习 SOLID 中的 L&#xff1a;里氏替换原则。它的英文翻译是 Liskov Substitution Principle&#xff0c;缩写为 LSP。 英文原话是&#xff1a; Functions that use points of references of base classes must be able to use objects of derived classes withou…...

java实现图片转pdf,并通过流的方式进行下载(前后端分离)

首先需要导入相关依赖&#xff0c;由于具体依赖本人也不是记得很清楚了&#xff0c;所以简短的说一下。 iText&#xff1a;PDF 操作库&#xff0c;用于创建和操作 PDF 文件。可通过 Maven 或 Gradle 引入 iText 依赖。 MultipartFile&#xff1a;Spring 框架中处理文件上传的类…...

如何系统的学习Python——Python的基本语法

学习Python的基本语法是入门的第一步&#xff0c;以下是一些常见的基本语法概念&#xff1a; 注释&#xff1a; 用#符号来添加单行注释&#xff0c;或使用三引号(或""")来添加多行注释。 # 这是一个单行注释 这是 多行 注释 变量和数据类型&#xff1a; 变量用…...

相机,棱镜和光场

一、成像方法 Imaging Synthesis Capture 1.Synthesis&#xff08;图形学上&#xff09;合成&#xff1a;比如之前学过的光线追踪或者光栅化 2.Capture&#xff08;捕捉&#xff09;&#xff1a;把真实世界存在的东西捕捉成为照片 二、相机 1.小孔成像 利用小孔成像的相…...

【图像版权】论文阅读:CRMW 图像隐写术+压缩算法

不可见水印 前言背景介绍ai大模型水印生成产物不可见水印CRMW 在保护深度神经网络模型知识产权方面与现有防御机制有何不同&#xff1f;使用图像隐写术和压缩算法为神经网络模型生成水印数据集有哪些优势&#xff1f;特征一致性训练如何发挥作用&#xff0c;将水印数据集嵌入到…...

代码随想录算法训练营第31天—贪心算法05 | ● 435. 无重叠区间 ● *763.划分字母区间 ● *56. 合并区间

435. 无重叠区间 https://programmercarl.com/0435.%E6%97%A0%E9%87%8D%E5%8F%A0%E5%8C%BA%E9%97%B4.html 考点 贪心算法重叠区间 我的思路 先按照区间左坐标进行排序&#xff0c;方便后续处理进行for循环&#xff0c;循环范围是0到倒数第二个元素如果当前区间和下一区间重叠…...

2024《》

vue-cli到哪做了那些事 vue-cli是vue.js的脚手架&#xff0c;用于自动生成vue.jswebpack的项目模板&#xff0c;快速搭建Vue.js项目。 vue cli内置了webpack的一些功能&#xff0c;这些是用webpack打包时需要我们自己配置的&#xff0c;例如&#xff1a; 1.ES6代码转换成ES5代…...

【Web】Java反序列化之从CC3看TemplatesImpl的利用

目录 关于TemplatesImpl 关于TemplatesImpl加载字节码 CC3链分析 纯CC3demo 根据CC3改CC6 关于TemplatesImpl TemplatesImpl 是 Java 中的一个类&#xff0c;通常与 Java 反序列化漏洞相关的攻击中被使用。该类位于 Java 标准库中的 javax.xml.transform 包下。 在 Java…...

【Elasticsearch索引】Recovery恢复索引

文章目录 索引恢复恢复列表获取恢复信息响应详细信息正在进行的恢复响应解析高级设置 本地分片恢复事务日志 索引恢复 索引恢复提供了对正在进行的索引分片恢复的洞察。恢复状态可以针对特定的索引报告&#xff0c;也可以在集群范围内报告。 恢复列表 recovery命令是索引分片…...

如何在 Linux 中快速清空文件而不删除它们?

在Linux系统中&#xff0c;清空文件而不删除它们是一种常见的需求&#xff0c;特别是在需要保留文件结构或权限的情况下。本文将详细介绍如何在Linux环境中快速清空文件内容的多种方法&#xff0c;以及每种方法的优缺点。清空文件通常涉及到文件内容的擦除&#xff0c;但并不涉…...

SpringBoot 配置文件${variable:default}用法

${variable:default}用法&#xff0c;variable​是变量名&#xff0c;default​是默认值。如果配置文件中未指定该变量的值&#xff0c;则会使用默认值来替代。 解释代码&#xff1a; ip: ${NACOS_IP:nacos.ip} 该yaml函数是一个配置项&#xff0c;用来指定Nacos服务器的IP地…...

CUDA学习笔记02:测试程序hello world

参考资料 Win10下在VS2019中配置使用CUDA进行加速的C项目 &#xff08;配置.h文件&#xff0c;.dll以及.lib文件等&#xff09;_vs2019 cuda-CSDN博客 配置流程 1. 新建一个一般的项目 2. 项目建好后&#xff0c;在项目里添加.cu测试文件 测试的.cu文件命名为cuda_utils.cu&…...

2023年第十四届蓝桥杯大赛软件类省赛C/C++大学A组真题

2023年第十四届蓝桥杯大赛软件类省赛C/C大学A组部分真题和题解分享 文章目录 蓝桥杯2023年第十四届省赛真题-平方差思路题解 蓝桥杯2023年第十四届省赛真题-更小的数思路题解 蓝桥杯2023年第十四届省赛真题-颜色平衡树思路题解 蓝桥杯2023年第十四届省赛真题-买瓜思路题解 蓝桥…...

项目部署发布

目录 上传数据库 修改代码中的数据源配置 修改配置文件中的日志级别和日志目录 打包程序 ​编辑​编辑 上传程序 查看进程是否在运行 以及端口 云服务器开放端口(项目所需要的端口) 上传数据库 通过xshell控制服务器 创建目录 mkdir bit_forum 然后进入该目录 查看路…...

MATLAB环境下基于离散小波变换的心电信号伪影去除及PQRST波检测

可穿戴个人健康监护系统被广泛认为是下一代健康监护技术的核心解决方案。监护设备不断地感知、获取、分析和存储大量人体在日常活动中的生理数据&#xff0c;为人体的健康状况提供必要的、准确的、集成的和长期的评估和反馈。在心电监测领域&#xff0c;可穿戴传感器具有以下应…...

SwiftUI 在 App 中弹出全局消息横幅(下)

功能需求 在 SwiftUI 开发的 App 界面中,有时我们需要在全局层面向用户展示一些消息: 如上图所示:我们弹出的全局消息横幅位于所有视图之上,这意味这它不会被任何东西所遮挡;而且用户可以点击该横幅关闭它。这是怎么做到的呢? 在本篇博文中,您将学到以下内容 功能需求…...

2023年06月CCF-GESP编程能力等级认证Scratch图形化编程三级真题解析

本文收录于专栏《Scratch等级认证CCF-GESP真题解析》,专栏总目录・点这里 一、单选题(共15题,共30分) 第1题 高级语言编写的程序需要经过以下( )操作,可以生成在计算机上运行的可执行代码。 A:编辑 B:保存 C:调试 D:编译 答案:D 第2题 小球角色,执行以下程序…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

Robots.txt 文件

什么是robots.txt&#xff1f; robots.txt 是一个位于网站根目录下的文本文件&#xff08;如&#xff1a;https://example.com/robots.txt&#xff09;&#xff0c;它用于指导网络爬虫&#xff08;如搜索引擎的蜘蛛程序&#xff09;如何抓取该网站的内容。这个文件遵循 Robots…...

leetcodeSQL解题:3564. 季节性销售分析

leetcodeSQL解题&#xff1a;3564. 季节性销售分析 题目&#xff1a; 表&#xff1a;sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...