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

Golang leetcode142 环形链表 暴力map 快慢指针法

文章目录

  • 环形链表 leetcode142
    • 暴力遍历 map哈希记录
    • 快慢指针法

环形链表 leetcode142

该题目要求找到入环的第一个节点
我们可以通过map进行记录,没到新的节点查询是否经过原有节点
入环节点,上两个节点的next相同
若有入环节点,则一定能检测到;若没有,则总会到达最后节点

暴力遍历 map哈希记录

// 暴力遍历 map哈希表记录
func detectCycle(head *ListNode) *ListNode {dummyHead := &ListNode{Next: head}table := map[*ListNode]int{}//若不成环,会走出循环for dummyHead.Next != nil {if _, ok := table[dummyHead.Next]; ok {return dummyHead.Next}table[dummyHead.Next] = 1dummyHead = dummyHead.Next}return nil
}

时间、空间复杂度都为O(n)

快慢指针法

思路解析

  1. 什么如果成环,快指针一定会再慢指针没有转完一圈之前追上满指针?

    1. 由于快指针的移动速度为2,慢指针的移动速度为1, 二者相对速度为1
      所以当快指针跟在慢指针后面时有以下几种情况

      • 快指针落后2 -> 快指针落后1 ->重合
      • 快指针落后1 ->** 重合**
      • 快指针与慢指针重合
        所以说只要快指针从后面追上慢指针,一定重合
    2. 最极端的情况:刚进入节点时,慢指针此时在相交节点上,快指针在慢指针前面一个
      在这里插入图片描述

      • 我们设到相遇所需的步数为x环长为n
      • 当相遇时,应该两个指针走过的节点数相同
      • 快指针由于是转了一圈再追上慢指针,其长度计算前去圈长
      • 快指针初始+1,LENfast=2x+1-n
      • 慢指针长度LENslow=x
      • 二者相同时,2x+1-n=x -> x=n-1
        也就是说即使在最极端的情况下也能在慢指针还没走完第一圈,到倒数第一个节点时与快指针相遇
  2. 得到二者一定相遇时,我们如何确定到底哪个节点是入环节点?
    在这里插入图片描述

    • 到相遇时,快指针走过的总距离F=a+n(b+c)+b ,n为快指针转过的圈数
    • 慢指针走过的距离S=a+b
    • 此时S=F,即a+n(b+c)+c=a+b -> a=(n-1)(b+c)+c
    • 通过这个方程我们可以看出来初始节点距离相交节点的距离为 n-1圈 圈长加c,而相遇节点距相交节点的距离为c
    • 所以从相遇节点和初始节点各出一个指针,总会在慢指针走完n-1圈在走玩c后在相交节点相遇
      在这里插入图片描述
// 双指针法 快慢指针
func detectCycle(head *ListNode) *ListNode {
fast, slow := head, head
//若有相交节点,则快慢指针一定会相遇
for fast != nil && slow != nil {
slow = slow.Next//防止fast指针超出链表限制
if fast.Next == nil {
return nil
}fast = fast.Next.Next//从相遇节点开始寻找相交节点
if fast == slow {
//题目要求不修改链表
p := head
for p != slow {
slow = slow.Next
p = p.Next
}return p}
}
return nil
}

相关文章:

Golang leetcode142 环形链表 暴力map 快慢指针法

文章目录 环形链表 leetcode142暴力遍历 map哈希记录快慢指针法 环形链表 leetcode142 该题目要求找到入环的第一个节点 我们可以通过map进行记录,没到新的节点查询是否经过原有节点 入环节点,上两个节点的next相同 若有入环节点,则一定能检…...

基于java,springboot的论旅游管理系统设计与实现

环境以及简介 基于java,springboot的论旅游管理系统设计与实现,Java项目,SpringBoot项目,含开发文档,源码,数据库以及ppt 源码下载 环境配置: 框架:springboot JDK版本:JDK1.8 服…...

掌握视频节奏,玩转剪辑艺术!,轻松调整视频播放速度与秒数的技巧大揭秘

你是否经常觉得视频播放得太快或太慢,无法满足你的观看需求?或者想要控制视频的长度,却不知道该如何下手?今天,我们将为你揭秘几种简单又实用的方法,让你轻松调整视频的播放速度和秒数! 首先&a…...

51单片机介绍

1 单片机简介 单片机,英文Micro Controller Unit,简称MCU 内部集成了CPU、RAM、ROM、定时器、中断系统、通讯接口等一系列电脑的常用硬件功能 单片机的任务是信息采集(依靠传感器)、处理(依靠CPU)和硬件设…...

k8s存储卷之动态

动态pv需要两个组件 1、卷插件,k8s本身支持的动态pv创建不包含NFS,需要声明和安装一个外部插件 Provisioner 存储分配器,动态创建pv,然后根据pvc的请求自动绑定和使用 2、StorageClass,用来定义pv的属性&#xff0c…...

base64 图片进行编码、解码;api调用

1、base64 图片进行编码、解码 编码 import base64# 假设您有一个图像文件,例如 image.jpg with open(r"C:\Users\l****1686722996428308480-1 (1).jpg", rb) as image_file:# 读取图像文件的二进制数据image_data image_file.read()# 将二进制数据编码…...

鸿蒙OS应用开发之百分比显示组件

前面学习了动态加载的组件,在本文里将要学习百分比显示组件,这个组件可以把数据按百分比的情况进行图形显示出来。百分比图形显示还是很有用的,比如一个班里学生的成绩占比,还有软件项目开发进度的情况,还有软件下载进度等等。 在鸿蒙系统里定义这个组件接口如下: DataP…...

网络多线程开发小项目--QQ登陆聊天功能(私聊群发)

9.1.4、QQ登陆聊天功能(私聊群发) 9.1.4.1、私聊功能 1、需求说明 2、思路分析 3、代码实现 QQClient: 1)cn.com.agree.qqclient.QQView.QQView case "3":log.debug("请输入想给谁发消息(在线用户):");St…...

企业版多域名SSL证书

多域名SSL证书,是一种数字证书,可以用一张SSL证书保护多个独立的域名。这种证书类型适用于拥有多个不同域名的个人或者企事业单位,可以节省给每个域名购买和管理SSL证书的时间和成本。企业版多域名SSL证书只支持企事业单位申请,今…...

理解Herbrand Equivalence

笔者最近在看GVN的一系列论文,总会看到一个概念叫Herbran Equivalence,依靠这种定义,能够判断一个GVN算法是否是complete的,也即检测一个算法是否是precise的,只有找到所有Herbrand Equivalence关系的算法才能称得上是…...

【SimPy系列博客之官方example学习与解读】—— Example 3: Car Wash

Hello,CSDN的各位小伙伴们,又见面啦!今天我们要学习的例程是:Car Wash!我们开始吧! 例程背景 这个例程相对于example 2来说会简单一些,有一个洗车厂,里面有若干台洗车机器&#xf…...

前端随机验证码安全验证sdk

前端随机验证码安全验证sdk 前言介绍一、效果展示二、使用步骤1.引入库2.参数说明3.方法与事件说明4.如何通过API获取当前用户的验证状态 ​ 前端必备工具推荐网站(免费图床、API和ChatAI等实用工具): http://luckycola.com.cn/ 前言 验证码:是一种校验区分用户是…...

语境化语言表示模型

一.语境化语言表示模型介绍 语境化语言表示模型(Contextualized Language Representation Models)是一类在自然语言处理领域中取得显著成功的模型,其主要特点是能够根据上下文动态地学习词汇和短语的表示。这些模型利用了上下文信息&#xf…...

PDO【配置】

PDOr: 6040 控制字 6060 模式 6083 加速度 6084 减速度 =====================【定位1】:// 补间7 607A 定位位置 6081 定位速度 =====================【速度3】: 60FF 目标速度 =====================【力矩4…...

CMake入门教程【高级篇】管理MSVC编译器警告

😈「CSDN主页」:传送门 😈「Bilibil首页」:传送门 😈「动动你的小手」:点赞👍收藏⭐️评论📝 文章目录 1.什么是MSVC?2.常用的屏蔽警告3.MSVC所有警告4.target_compile_options用法5.如何在CMake中消除MSVC的警告?6.屏蔽警告编写技巧...

【JaveWeb教程】(8)Web前端基础:Vue组件库Element之Table表格组件和Pagination分页组件 详细示例介绍

目录 1 Table表格组件1.1 组件演示1.2 组件属性详解 2 Pagination分页2.1 组件演示2.2 组件属性详解2.3 组件事件详解 接下来我们来学习一下ElementUI的常用组件,对于组件的学习比较简单,我们只需要参考官方提供的代码,然后复制粘贴即可。本节…...

llama_index 创始人为我们展示召回提升策略(提升15%)

用句子向量替换为句子向量 句子检索,将句子转化为向量。在检索的过程中,假如句子命中,则将句子周围的内容也当做检索内容。 对比句子检索和之前的按块去做切分的检索。可以看到,内容的相关性提升了8%, 构建数据的时候…...

RAG 详解

原文:GitHub - Tongji-KGLLM/RAG-Survey 目录 RAG调查 什么是RAG?RAG的范式 幼稚的 RAG高级 RAG模块化 RAG如何进行增强?RAG 还是微调?如何评估 RAG?前景 严峻的挑战多式联运扩展RAG的生态系统RAG论文清单 增强阶段 …...

【llm 部署运行videochat--完整教程】

# 申请llama权重 https://ai.meta.com/resources/models-and-libraries/llama-downloads/ -> 勾选三个模型 -> 等待接收右键信息 # 下载llama代码库 git clone https://github.com/facebookresearch/llama.git cd llama bash download.py -> email -> url …...

Talking about likes

Tutorial Hi! Tim here with another 925English lesson! In today’s lesson, we’re learning how to talk about likes and preferences. Why It’s Important: Talking about things we like is common in various situations, from meetings to casual chats over lunch…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向: 逆向设计 通过神经网络快速预测微纳结构的光学响应,替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码,写上注释 当然可以!这段代码是 Qt …...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包: for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

【网络安全】开源系统getshell漏洞挖掘

审计过程: 在入口文件admin/index.php中: 用户可以通过m,c,a等参数控制加载的文件和方法,在app/system/entrance.php中存在重点代码: 当M_TYPE system并且M_MODULE include时,会设置常量PATH_OWN_FILE为PATH_APP.M_T…...

jdbc查询mysql数据库时,出现id顺序错误的情况

我在repository中的查询语句如下所示&#xff0c;即传入一个List<intager>的数据&#xff0c;返回这些id的问题列表。但是由于数据库查询时ID列表的顺序与预期不一致&#xff0c;会导致返回的id是从小到大排列的&#xff0c;但我不希望这样。 Query("SELECT NEW com…...

Spring AOP代理对象生成原理

代理对象生成的关键类是【AnnotationAwareAspectJAutoProxyCreator】&#xff0c;这个类继承了【BeanPostProcessor】是一个后置处理器 在bean对象生命周期中初始化时执行【org.springframework.beans.factory.config.BeanPostProcessor#postProcessAfterInitialization】方法时…...

C++11 constexpr和字面类型:从入门到精通

文章目录 引言一、constexpr的基本概念与使用1.1 constexpr的定义与作用1.2 constexpr变量1.3 constexpr函数1.4 constexpr在类构造函数中的应用1.5 constexpr的优势 二、字面类型的基本概念与使用2.1 字面类型的定义与作用2.2 字面类型的应用场景2.2.1 常量定义2.2.2 模板参数…...

湖北理元理律师事务所:债务清偿方案中的法律技术革新

文/金融法律研究组 当前债务服务市场存在结构性矛盾&#xff1a;债权人追求快速回款&#xff0c;债务人需要喘息空间。湖北理元理律师事务所通过创新法律技术&#xff0c;在《企业破产法》《民法典》框架下构建梯度清偿模型&#xff0c;实现多方利益平衡。 一、个人债务优化的…...

[electron]预脚本不显示内联script

script-src self 是 Content Security Policy (CSP) 中的一个指令&#xff0c;它的作用是限制加载和执行 JavaScript 脚本的来源。 具体来说&#xff1a; self 表示 当前源。也就是说&#xff0c;只有来自当前网站或者当前页面所在域名的 JavaScript 脚本才被允许执行。"…...

基于机器学习的智能故障预测系统:构建与优化

前言 在现代工业生产中&#xff0c;设备故障不仅会导致生产中断&#xff0c;还会带来巨大的经济损失。传统的故障检测方法依赖于人工巡检和定期维护&#xff0c;这种方式效率低下且难以提前预测潜在故障。随着工业物联网&#xff08;IIoT&#xff09;和机器学习技术的发展&…...