【链表OJ】相交链表 环形链表1
前言:
💥🎈个人主页:Dream_Chaser~ 🎈💥
✨✨刷题专栏:http://t.csdn.cn/UlvTc
⛳⛳本篇内容:力扣上链表OJ题目
目录
一.leetcode 160. 相交链表
1.问题描述:
2.解题思路:
二.leetcode 141.环形链表
1.问题描述:
2.代码思路:
3.问题证明:
一.leetcode 160. 相交链表
来源:160. 相交链表 - 力扣(LeetCode)
1.问题描述:
给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回NULL 。
图示两个链表在节点c1开始相交:
已知a1与b1的头结点地址,并分别用headA和headB指针指向
- 题目数据 保证 整个链式结构中不存在环。
- 注意,函数返回结果后,链表必须 保持其原始结构 。
题目接口:
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{}
2.解题思路:
原始链表:
- 首先定义tailA和tailB分别遍历a链表和b链表,在遍历过程中,分别求出两链表长度,分别定义为lenA和lenB,然后用lenA和lenB相减取差的绝对值,计为差距步gap
- 然后定义指向长链表的指针longList,和指向短链表的指针shortList,用前面定义的LenA和LenB比较它们的长度,进行合适赋值,接着让长的链表走差距步gap。若长链表结点的地址不等于短链表,则让tailA和tailB指针继续走,有相等结点则跳出循环,返回此时的longList或者shortList。
实现代码:
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {struct ListNode* tailA = headA;struct ListNode* tailB = headB;int lenA = 1, lenB = 1;//原始长度定义为1才是正确的while (tailA){tailA = tailA->next;lenA++;}while (tailB){tailB = tailB->next;lenB++;}if (tailA != tailB)//若两指针到结束也找不到相等结点,则返回NULLreturn NULL;int gap = abs(lenA - lenB);//取出两者相减的绝对值,赋值给gap表示两链表的差距步struct ListNode*longList = headA;//先假定A链表为长链表struct ListNode* shortList = headB;if (lenA < lenB)//接着两链表比较,如果满足此条件,则重新赋值,定义B链表的为长链表{longList = headB;shortList = headA;}while (gap--)//长链表先走差距步{longList = longList->next;}while (longList != shortList)//若没有相等(地址相等)则继续遍历{longList = longList->next;shortList = shortList->next;}return shortList; }
代码执行:
二.leetcode 141.环形链表
1.问题描述:
给你一个链表的头节点
head
,判断链表中是否有环。如果链表中有某个节点,可以通过连续跟踪
next
指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数pos
来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos
不作为参数进行传递 。仅仅是为了标识链表的实际情况。如果链表中存在环 ,则返回
true
。 否则,返回false
。
题解接口:
bool hasCycle(struct ListNode *head) {}
2.代码思路:
本题的代码思路:
定义一个快指针,让其先走两步,接着定义一个慢指针,一次走一步,反复此循环。
- 如果快慢指针指向的地址相等,则证明链表中存在环。
- 如果快指针提前指向NULL,循环结束,则证明不是环形链表,直接返回false。
函数实现
bool hasCycle(struct ListNode *head) {struct ListNode* fast=head,*slow =head;while(fast && fast->next){fast=fast->next->next;//快指针先走两步,慢指针走一步slow=slow->next; //慢指针走一步if(fast==slow)//指针相遇表明链表带环{return true;}}return false;//否则返回NULL }
代码执行:
然而本题的重点在于如何证明上面的代码的实现逻辑,是一个数学问题。
3.问题证明:
1、slow和fast一定会相遇吗?
答:一定会
画一张图来证明一下, 此时两指针同时指向头节点的地址。
接着先让快指针fast=fast->next->next(快指针先走两步),后让 slow=slow->next(慢指针走一步).
fast会先进环,slow会后进环,假设slow进环时,slow和fast之间的距离为N
slow进环以后,fast开始追击slow,slow每走1步,fast每走2步,他们之间距离缩小1。
2、slow走1步,fast走n(3/4/5….)步可以吗?(n > 2)
不一定
举例:
slow每次走一步,fast每次走三步,它们一定可以相遇吗?答:不一定。
画图
当快慢指针之间的距离个数为奇数时
fast会先进环,slow会后进环,假设slow进环时, slow和fast之间的距离为N
slow进环以后,fast开始追击slow,slow每走1步,fast每走3步,他们之间距离缩小2
当快指针追赶上慢指针时,此时错过了,并进入新一轮的追击,假设一个值C为环的长度,那么快慢指针的距离此时必为C-1
所以,如果C-1是奇数那么fast永远追不上slow
当C-1的距离为偶数时,那么此时的距离变化为
N N-2 N-4 ... 4 2 0 ,0则表示此时两指针相遇,表明下一轮可以追上。
本文结束,如有错误,我会继续更新关于链表oj的题目,欢迎大家指正!
相关文章:
【链表OJ】相交链表 环形链表1
前言: 💥🎈个人主页:Dream_Chaser~ 🎈💥 ✨✨刷题专栏:http://t.csdn.cn/UlvTc ⛳⛳本篇内容:力扣上链表OJ题目 目录 一.leetcode 160. 相交链表 1.问题描述: 2.解题思路: 二.leetcode 141.环形链表 …...
DevOps之自动化测试
什么是自动化测试? 明确一下自动化测试不是什么。自动化测试不是指自动化生成测试代码,而是自动化地执行由开发人员或测试人员编写的测试代码。正如下面这句谚语:“绝不要手工去做任何可以被自动化处理的事情。——Curt Hibbs” 之前是由人…...
Java 程序打印 OpenCV 的版本
我们可以使用 Java 程序来使用 OpenCV。 OpenCV 的使用需要动态库的加载才可以。 加载动态库 到 OpenCV 的官方网站上下载最新的发布版本。 Windows 下载的是一个可执行文件,没关系,这个可执行文件是一个自解压程序。 当你运行以后会提示你进行解压。…...
ChatGPT⼊门到精通(2):ChatGPT 能为我们做什么
⼀、雇佣免费的⼲活⼩弟 有了ChatGPT后,就好⽐你有了好⼏个帮你免费打⼯的「⼩弟」,他们可以帮你做很多 ⼯作。我简单总结⼀些我⽬前使⽤过的⽐较好的基于ChatGPT的服务和应⽤。 1、总结、分析 当我们在阅读⼀些⽂章和新闻的时候,有的⽂章写…...
线程和进程的区别是什么?
线程(Thread)和进程(Process)是操作系统中两个重要的概念,用于管理程序的执行。它们有以下区别: 定义:进程:进程是程序的一个执行实例,它包含了程序的代码、数据以及执行上下文。进程是操作系统分配资源和调度的基本单位。线程:线程是进程的子执行单元,一个进程可以…...
力扣27.移除元素
27. 移除元素 提示 简单 1.9K 相关企业 给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。 不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。 元素的顺序…...
指针(个人学习笔记黑马学习)
1、指针的定义和使用 #include <iostream> using namespace std;int main() {int a 10;int* p;p &a;cout << "a的地址为:" << &a << endl;cout << "a的地址为:" << p << endl;…...
vue 路由动态加载
在 Vue.js 中,可以使用 webpack 的动态导入语法来实现路由动态加载。下面是一个简单的示例: const Home () > import(/* webpackChunkName: "home" */ ./views/Home.vue); const About () > import(/* webpackChunkName: "about…...
电脑识别不了固态硬盘怎么办?
在使用固态硬盘时,可能会出现电脑无法识别的情况,这时我们就无法使用固态硬盘中的数据。那么,电脑识别不了固态硬盘怎么办? 为什么电脑识别不了固态硬盘? 一般来说,电脑识别不了固态硬盘是因为以下3个原因…...
QCustomPlot 绘制卡顿问题
大数据量导致曲线绘制卡顿问题 这里提供一个思路在跟踪源码中发现底层卡顿在vector的resize() 此处扩容中 所以尽量使用下面的接口 /*! \overloadAdds the provided data point as \a key and \a value to the current data.Alternatively, you can also access and modify t…...
uni-app开发小程序,radio单选按钮,点击可以选中,再次点击可以取消
一、实现效果: 二、代码实现: 不适用官方的change方法,自己定义点击方法。 动态判断定义的值是否等于遍历的值进行回显,如果和上一次点击的值一样,就把定义的值改为null <template><view><radio-group&…...
【Qt专栏】实现单例程序,禁止程序多开的几种方式
目录 一,简要介绍 二,实现示例(Windows) 1.使用系统级别的互斥机制 2.通过共享内存(进程间通信-IPC) 3.使用命名互斥锁(不推荐) 4.使用文件锁 5.通过网络端口检测 一…...
力扣26. 删除有序数组中的重复项
给你一个 升序排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。 考虑 nums 的唯一元素的数量为 k ,你需要做…...
【机器学习】鸢尾花分类-逻辑回归示例
这段代码是一个完整的示例,展示了如何使用逻辑回归对鸢尾花数据集进行训练、保存模型,并允许用户输入数据进行预测。以下是对这段代码的总结:功能: 这段代码演示了如何使用逻辑回归对鸢尾花数据集进行训练,并将训练好的…...
Flink CDC介绍
1.CDC概述 CDC(Change Data Capture)是一种用于捕获和处理数据源中的变化的技术。它允许实时地监视数据库或数据流中发生的数据变动,并将这些变动抽取出来,以便进行进一步的处理和分析。 传统上,数据源的变化通常通过…...
Java集合sort排序报错UnsupportedOperationException处理
文章目录 报错场景排查解决UnmodifiableList类介绍 报错场景 我们使用的是PostgreSQL数据库,存储业务数据,业务代码使用的是Spring JPA我们做的是智慧交通信控平台,有个功能是查询展示区域的交通态势,需要按照不同维度排序展示区…...
安防监控/磁盘阵列存储/视频汇聚平台EasyCVR调用rtsp地址返回的IP不正确是什么原因?
安防监控/云存储/磁盘阵列存储/视频汇聚平台EasyCVR可拓展性强、视频能力灵活、部署轻快,可支持的主流标准协议有GB28181、RTSP/Onvif、RTMP等,以及厂家私有协议与SDK接入,包括海康Ehome、海大宇等设备的SDK等,能对外分发RTSP、RT…...
Spring boot开启定时任务
Cron表达式生成器 基于接口的方式 使用Scheduled 注解很方便,但缺点是当我们调整了执行周期的时候,需要重启应用才能生效,这多少有些不方便。为了达到实时生效的效果,那么可以使用接口来完成定时任务,统一将定时器信…...
package.json相关知识记录
一、相关字段 npm官方字段介绍 🍧 bin > 简单理解:指定命令的名称及路径 🍉 相当于想path中添加路径,局部安装是在./node_modules/.bin/,全局安装是在全局的bin目录 🍉 bin指定的文件必须…...
VueRouter使用详解(5000字通关大全)
Vue Router是一个官方的路由管理器,它可以让我们在Vue应用中实现单页面应用(SPA)的效果,即通过改变URL而不刷新页面来显示不同的内容。Vue Router可以让我们定义多个路由,每个路由对应一个组件,当URL匹配到…...
vue axios实现下载文件及responseType:blob注意事项
需要使用axios和js-file-download组件 npm install js-file-download --save npm install axios --save import fileDownload from fileDownload; // 引入fileDownload import axios from axios; // 引入axios axios({method: get,url: xxxxxxx,responseType: blob }).then(r…...
StringBuilder类分享(1)
一、StringBuilder说明 StringBuilder是一个可变的字符序列。这个类提供了一个与StringBuffer兼容的API,但不保证同步,即StringBuilder不是线程安全的,而StringBuffer是线程安全的。显然,StringBuilder要运行的更快一点。 这个类…...
Qt 打开文件列表选择文件,实现拖拽方式打开文件
1. 实现打开文件列表选择文件 1.1. 创建 Qt 工程,并添加几个简单控件 这里笔者选用的是 QMainWindow,创建好工程后在 ui 界面设计中添加 QLineEdit、QPushBtton至少这两个控件,如下图摆放。 1.2. 头文件中添加相关操作 在 mainwindow.h 中…...
[C/C++]天天酷跑游戏超详细教程-上篇
个人主页:北海 🎐CSDN新晋作者 🎉欢迎 👍点赞✍评论⭐收藏✨收录专栏:C/C🤝希望作者的文章能对你有所帮助,有不足的地方请在评论区留言指正,大家一起学习交流!ǹ…...
5G NR:RACH流程 -- Msg1之选择正确的PRACH时频资源
PRACH的时域资源是如何确定的 PRACH的时域资源主要由参数“prach-ConfigurationIndex”决定。拿着这个参数的取值去协议38211查表6.3.3.2-2/3/4,需要注意根据实际情况在这三张表中进行选择: FR1 FDD/SULFR1 TDDFR2 TDD Random access preambles can onl…...
在vue3项目中编辑的时候,解决对话框里边的数据和列表中的数据联动了。深复制
//分析原因是从列表中拿到的数据直接复制去修改就涉及到堆里变的内容是一样的,直接复制其实只是把引用地址赋值给变量了,解决方法是 浅复制和深复制。<!-- 审批流程管理 --> <template><div style"float: left; width: 250px;backgr…...
循环结构(个人学习笔记黑马学习)
while循环语句 在屏幕中打印0~9这十个数字 #include <iostream> using namespace std;int main() {int i 0;while (i < 10) {cout << i << endl;i;}system("pause");return 0; } 练习案例: 猜数字 案例描述:系统随机生成一个1到100之间的数字&…...
ceph中PGLog处理流程
正文 struct pg_log_entry_t {ObjectModDesc mod_desc; //用于保存本地回滚的一些信息,用于EC模式下的回滚操作bufferlist snaps; //克隆操作,用于记录当前对象的snap列表hobject_t soid; …...
macOS使用命令行连接Oracle(SQL*Plus)
Author: histonevonzohomail.com Date: 2023/08/25 文章目录 SQL\*Plus安装下载环境配置 SQL\*Plus远程连接数据库参考文献 原文地址:https://histonevon.top/archives/oracle-mac-sqlplus数据库安装:Docker安装Oracle数据库 (histonevon.top) SQL*Plus…...
Mac下使用Homebrew安装MySQL5.7
Mac下使用Homebrew安装MySQL5.7 1. 安装Homebrew & Oh-My-Zsh2. 查询软件信息3. 执行安装命令4. 开机启动5. 服务状态查询6. 初始化配置7. 登录测试7.1 终端登录7.2 客户端登录 参考 1. 安装Homebrew & Oh-My-Zsh mac下如何安装homebrew MacOS安装Homebrew与Oh-My-Zsh…...
centos安装Nginx配置Nginx
1. 查看操作系统有没有安装Nginx which nginx 2. 使用epel的方式进行安装(方法二) 先安装epel sudo yum install yum-utils 安装完成后,查看安装的epel包即可 sudo yum install epel 3 开始安装nginx 上面的两个方法不管选择哪个&…...
Linux环境下搭建使用缓存中间件Redis
缓存中间件Redis搭建与使用 前言正文1 提供安装环境2 下载安装3 修改启动配置4 启动服务5 使用6 关闭服务7 卸载 前言 redis服务将在linux系统中部署,本文前提是已经搭建一个linux系统,并配置好网络等。使用vmware搭建一个linux系统,可以参考…...
Oracle 本地客户端连接远程 Oracle 服务端并使用 c# 连接测试
这里写自定义目录标题 前言Oracle 客户端安装先决条件下载 Oracle 客户端Oracle 客户端环境变量配置 PL/SQLPL/SQL 下载PL/SQL 配置 配置远程连接tnsnames.ora 文件配置 使用 PL/SQL 连接远程数据库使用 C# 远程访问 Oracle 数据库结语 前言 最近有一个需要使用本地的 Oracle …...
java中上传文件先下载到本地再上传还有就是直接通过文件流url地址进行上传优缺点?
在Java中上传文件到SFTP服务器时,有两种常见的方法:先下载到本地再上传和直接使用文件流URL地址进行上传。每种方法都有其优点和缺点,下面是对它们的简要比较: 先下载到本地再上传: 优点: 可以在本地对文件…...
华为复合vlan(mux vlan)
一、概念: Multiplex vlan:实现网络资源控制的的机制。 / Principle vlan:port 可以和mux vlan内所有接口进行通信,限制128个 < /Separate vlan:隔离型从vlan,只能和…...
第62步 深度学习图像识别:多分类建模(Pytorch)
基于WIN10的64位系统演示 一、写在前面 上期我们基于TensorFlow环境做了图像识别的多分类任务建模。 本期以健康组、肺结核组、COVID-19组、细菌性(病毒性)肺炎组为数据集,基于Pytorch环境,构建SqueezeNet多分类模型࿰…...
GPT带我学-设计模式-适配器模式
1 什么是适配器设计模式 适配器设计模式是一种结构性设计模式,用于在不兼容的接口之间进行转换。它允许将一个类的接口转换成客户端所期望的接口。 适配器模式包含以下几个角色: 目标接口(Target):定义客户端所期望…...
Pyecharts教程(七):使用pyecharts创建堆叠柱状图的示例
Pyecharts教程(七):使用pyecharts创建堆叠柱状图的示例 作者:安静到无声 个人主页 目录 Pyecharts教程(七):使用pyecharts创建堆叠柱状图的示例完整代码推荐专栏在数据可视化中,柱状图是一种常见的图表类型,它可以清晰地展示各类别之间的比较关系。然而,如果我们想要在同…...
C++中的强制转换的常用类型及应用场景详解
C中的强制转换的常用类型及应用场景详解 文章目录 C中的强制转换的常用类型及应用场景详解一、静态转换(static_cast)二、动态转换(dynamic_cast)三、常量转换(const_cast)四、重新解释转换(rei…...
ubuntu调整时区
ubuntu在新装系统的时候,所用的时区不一定是8的时区,需要设置一下,否则执行cron等定时任务的时候,时间就会不对 查看当前系统的时区 date -R tzselect 选择时区,但是没用 ,作用可能就是 选择时区 设置时区:…...
mybatis:动态sql【2】+转义符+缓存
目录 一、动态sql 1.set、if 2.foreach 二、转义符 三、缓存cache 1. 一级缓存 2. 二级缓存 一、动态sql 1.set、if 在update语句中使用set标签,动态更新set后的sql语句,,if作为判断条件。 <update id"updateStuent" pa…...
2021年09月 C/C++(五级)真题解析#中国电子学会#全国青少年软件编程等级考试
第1题:抓牛 农夫知道一头牛的位置,想要抓住它。农夫和牛都位于数轴上,农夫起始位于点N(0<=N<=100000),牛位于点K(0<=K<=100000)。农夫有两种移动方式: 1、从X移动到X-1或X+1,每次移动花费一分钟 2、从X移动到2*X,每次移动花费一分钟 假设牛没有意识到农夫的…...
Ansible学习笔记1
公司的服务器越来越多,维护一些简单的事情都会变得很繁琐。用Shell脚本来管理少量服务器效率还行,服务器多了,Shell脚本无法实现高效率运维。这种情况下,我们需要引入自动化运维工具,对多台服务器实现高效运维。 配置服…...
解决centos离线安装cmake找不到OpenSSL问题
安装方法:见另外一篇文章 https://blog.csdn.net/zhongxj183/article/details/118488629 按照文章下载了离线gcc 和OpenSSL,以及在cmake官网下载了最新版 cmake-3.27.4.tar.gz 顺利安装gcc 和OpenSSL 但执行编译cmake时,报错找不到OpenSSL…...
Java 中数据结构ArrayList的用法
Java ArrayList ArrayList 类是一个可以动态修改的数组,与普通数组的区别就是它是没有固定大小的限制,我们可以添加或删除元素。 方法集合样例代码 import java.util.*;public class list_set_iterator {public static void main(String[] args) {Lis…...
UDP 多播(组播)
前言(了解分类的IP地址) 1.组播(多播) 单播地址标识单个IP接口,广播地址标识某个子网的所有IP接口,多播地址标识一组IP接口。单播和广播是寻址方案的两个极端(要么单个要么全部)&am…...
分布式环境集成JWT(Java Web Token)
目录 一,说明:二,Token、Session和Cookie比较三,Spring Boot项目集成JWT1,引入依赖2,Token工具类3,定义拦截器4,注册拦截器5,编写登录代码6,测试 四ÿ…...
Python实战之数据表提取和下载自动化
在网络爬虫领域,动态渲染类型页面的数据提取和下载自动化是一个常见的挑战。本文将介绍如何利用Pyppeteer库完成这一任务,帮助您轻松地提取动态渲染页面中的数据表并实现下载自动化。 一、环境准备 首先,确保您已经安装了Python环境。接下来…...
Midjourney学习(三)6个高级应用
使用Remix Mode在原图片的基础上进行二次创作 通过prompt得到大图之后,点击Make Variations按钮,输入Remix Prompt,即可得到意想不到的效果! 局部内容重绘 通过局部重绘可以实现对画面内容更加精细化的控制,同样也是需…...
C语言:指针类型的意义
1.指针的类型决定了解引用时访问几个字节 2.指针的类型决定了指针1、-1跳过几个字节 一、指针的类型决定指针解引用时访问几个字节 例如 int 型指针解引用时访问4个字节 char 型指针解引用时访问1个字节 详解代码如下: int b 0x11223344(十六进制&…...