当前位置: 首页 > 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题 小球角色,执行以下程序…...

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用React Native…...

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

蓝桥杯3498 01串的熵

问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798&#xff0c; 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

springboot整合VUE之在线教育管理系统简介

可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生&#xff0c;小白用户&#xff0c;想学习知识的 有点基础&#xff0c;想要通过项…...

C#中的CLR属性、依赖属性与附加属性

CLR属性的主要特征 封装性&#xff1a; 隐藏字段的实现细节 提供对字段的受控访问 访问控制&#xff1a; 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性&#xff1a; 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑&#xff1a; 可以…...

【Linux】自动化构建-Make/Makefile

前言 上文我们讲到了Linux中的编译器gcc/g 【Linux】编译器gcc/g及其库的详细介绍-CSDN博客 本来我们将一个对于编译来说很重要的工具&#xff1a;make/makfile 1.背景 在一个工程中源文件不计其数&#xff0c;其按类型、功能、模块分别放在若干个目录中&#xff0c;mak…...

永磁同步电机无速度算法--基于卡尔曼滤波器的滑模观测器

一、原理介绍 传统滑模观测器采用如下结构&#xff1a; 传统SMO中LPF会带来相位延迟和幅值衰减&#xff0c;并且需要额外的相位补偿。 采用扩展卡尔曼滤波器代替常用低通滤波器(LPF)&#xff0c;可以去除高次谐波&#xff0c;并且不用相位补偿就可以获得一个误差较小的转子位…...

协议转换利器,profinet转ethercat网关的两大派系,各有千秋

随着工业以太网的发展&#xff0c;其高效、便捷、协议开放、易于冗余等诸多优点&#xff0c;被越来越多的工业现场所采用。西门子SIMATIC S7-1200/1500系列PLC集成有Profinet接口&#xff0c;具有实时性、开放性&#xff0c;使用TCP/IP和IT标准&#xff0c;符合基于工业以太网的…...