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

【经典面试题】是否形成有环链表

1.环形链表oj

在这里插入图片描述

2. oj解法

利用快慢指针
请添加图片描述

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {ListNode* slow = head, *fast = head;while(fast && fast -> next){fast = fast -> next -> next;slow = slow -> next;if(slow == fast){return true;}}return false;
}

3.面试加问

当然面试题不会这么容易,面试官随之抛下以下两个问题:
1.有没有可能快慢指针永远无法相遇呢?
2.如果快指针一次走3步,一次走4步,一次走n步还会不会相遇呢?

经过简单思考可以得出:当快指针一次走两步时,快慢指针每次行动的间隔值为1,那么此时当慢指针进入圆环开始被快指针追击时,必定会被追上。

那么如果快指针一次走三步呢?

有没有可能慢指针和快指针永远无法相遇呢?
这里进行简单的数学证明:

在这里插入图片描述
简单画图分析:
设链表从开始到进入环的长度为L,两指针在距换开始点的N的长度相遇,环长为C
从中可以得到哪些数学的等量关系式呢?
已知快指针的速度是慢指针的三倍,那么其走的路程也就是三倍,也就是每次追击两者之间的距离减少2

这里给出简单的思路图:
在这里插入图片描述
从图中可以看出

从图中可以看出当初始的N值为奇数时,且环长C为偶数时,两指针永远无法相遇。
那么现在就是要判断此种情况是否存在。

在这里插入图片描述
可推出此等式,从中我们可以发现,=左边为2L,永远为偶数,而右边为一个减式。
通过数学知识,我们得知当两数相减时,只有偶数-偶数或者奇数-奇数时得到偶数,所以当C为偶数时,(x+1)*C为偶数,此时N也为偶数,那么之前讨论的永远无法追上就时谬论了。
因此在进行第二轮追击时就可以追上,从而解得此题。

以及后面的快指针为4步N步都是同一解法。

如果被面试的是你,你答得出来吗?面试官先抛出一个简单代码题,随之考察面试者的数理分析能力,所以数学基础也是不可或缺的。

感谢大家的阅读,我将持续更新经典面试题。

相关文章:

【经典面试题】是否形成有环链表

1.环形链表oj 2. oj解法 利用快慢指针: /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode; bool hasCycle(struct ListNode *head) {ListNode* slow head, *fast…...

Flask 用 Redis 缓存键值对-实例

Flask 使用起 Redis 来简直就是手到擒来,比 MySQL 简单多了,不需要那么多配置,实际代码就这么多,直接复制就能用。除了提供简单实用的实例以外,本文后面还会简单介绍一下 Redis 的安装与使用,初学者也能一看…...

我的世界1.21多种服务端开服教程,原版/Forge/Fabric/Paper/Mohist...,Minecraft开服教程

Minecraft(MC)1.21版多种服务端开服教程,我的世界1.21服务器搭建教程,MC原版/Forge/Fabric/Paper/Mohist服务端搭建教程,我的世界MOD/插件服开服教程。 本教程使用 Linux系统MCSManager 面板来搭建Minecraft服务器。 …...

docker安装nginx并配置https

参考 docker安装nginx并配置https-腾讯云开发者社区-腾讯云 (tencent.com) 证书的生成 参见:SpringBoot项目配置HTTPS接口的安全访问(openssl配置)_配置接口访问-CSDN博客 步骤 1: 拉取Nginx镜像 docker pull nginx 好使的镜像如下&#x…...

永磁同步电机控制算法--基于 SVM 的无磁链环 DTC

永磁同步电机无磁链环 DTC 通过控制定子磁链交轴分量来直接控制转矩,不再要求控制磁链幅值恒定,省去了传统 DTC 中的磁链环,不仅转矩响应更快,有效抑制了转矩脉动,而且提高了电机功率因数。但无磁链环 DTC 方案仍采用传…...

如何避免在 Docker 容器中遇到 MAC 地址冲突和 IP 地址冲突的问题

在 Docker 容器中遇到 MAC 地址冲突和 IP 地址冲突的问题时,通常是由于 Docker 在分配网络资源时出现了一些问题。虽然这种情况并不常见,但仍有可能发生。以下是一些原因和可能的解决方案: 原因分析 Docker 版本问题:某些 Docke…...

arm64架构下源码编译安装kafka —— 筑梦之路

一般来说,直接使用官方提供的二进制文件即可,没有必要使用源码编译安装的方式,而对于有特殊用途的,选择源码编译安装无疑是更好地选择。比如修改源码实现想要的功能,mirrormaker2保持topic名称不变。 git clone https…...

LabVIEW前面板占满整个屏幕(转)

希望在运行一个LabVIEW程序时,它的前面板能够占据整个屏幕,且不显示Windows的任务栏或其他任何的LabVIEW菜单选项。怎样才能实现这一功能? 您可以通过手动配置或编程的方式实现该功能。 手动配置VI属性 您可以通过以下操作,将…...

Promise.all、any、race和allSettled的相同点与不同点与应用场景

在JavaScript中,Promise对象是一种处理异步操作的方式。它允许我们以一种更优雅的方式来处理异步代码,而不是使用回调函数。在Promise中,有一些方法可以帮助我们更好地管理多个Promise实例,这些方法包括Promise.all、Promise.any、…...

Ubuntu下如何设置程序include搜索路径及链接路径

添加库的include及lib路径 linux下系统默认路径为 /usr/include, /usr/local/include, gcc在编译程序时会按照当前目录路径->系统默认路径->系统环境变量的路径方式去查找,所以当我们想调用的库未安装在系统默认路径时,我们可以通过手动添加环境变…...

FLinkCDC引起的生产事故(二)

背景: 最近在做实时数据的抽取工作,利用FLinkCDC实时抽取目标库Oracle的数据到Doris中,但是在抽取的过程中,会导致目标库的生产库数据库非常卡顿,为了避免对生产环境的数据库造成影响,对生产环境的数据库利…...

【产品经理】WMS多仓调拨转移说明

对于仓储管理来说,越来越多企业开始应用WMS进行系统化的管理,以提升仓库的作业效率。本文作者从业务流程和基础功能两个方面展开介绍,希望对你有帮助。 一、业务流程 。在线下业务流程拓展,仓库不断增多的过程中,由于…...

每日一练:奇怪的TTL字段(python实现图片操作实战)

打开图片,只有四种数字:127,191,63,255 最大数字为255,想到进制转换 将其均转换为二进制: 发现只有前2位不一样 想着把每个数的前俩位提取出来,组成新的二进制,然后每…...

【Java开发实训】day03——方法的注意事项

目录 一、方法的基本概念 二、void和return关键字 三、单一返回点原则 四、static方法使用说明 🌈嗨!我是Filotimo__🌈。很高兴与大家相识,希望我的博客能对你有所帮助。 💡本文由Filotimo__✍️原创,首发于…...

HarmonyOS NEXT:一次开发,多端部署

寄语 这几年特别火的uni-app实现了“一次开发,多端使用”,它这个端指的是ios、安卓、各种小程序这些,而HarmonyOS NEXT也提出了“一次开发,多端部署”,而它这个端指的是终端设备,也就是我们的手机、平板、电…...

Bilibili Android一二面凉经(2024)

BiliBili Android一二面凉经(2024) 笔者作为一名双非二本毕业7年老Android, 最近面试了不少公司, 目前已告一段落, 整理一下各家的面试问题, 打算陆续发布出来, 供有缘人参考。今天给大家带来的是《BiliBili Android一二面凉经(2024)》。 面试职位: 高级Android开发工程师&…...

数据库内核研发学习之路(一)

已经上了几天班了,开始做一些总结性的工作。 数据库内核研发首当其中的便是环境配置,今天先介绍一下虚拟机之类的环境搭建,在之前已经写过一篇关于VMware搭建虚拟机的博客了,有兴趣可以去看看,这里我再总结一下使用Vi…...

LSTM:深度学习中的时间序列处理大师

LSTM:深度学习中的时间序列处理大师 引言 在深度学习领域,处理时间序列数据是一项极具挑战性的任务。时间序列数据广泛存在于金融、医疗、气象、自然语言处理等多个领域,这些数据不仅具有时间依赖性,还常常伴随着复杂的长期依赖…...

T113-i系统启动速度优化方案

背景: 硬件:T113-i + emmc 软件:uboot2018 + linux5.4 + QT应用 分支:longan 问题: 全志T113-i的官方系统软件编译出的固件,开机启动时间10多秒,启动时间太长,远远超过行业内linux系统的开机速度,需要进一步优化。 T113-i 优化后启动速度实测数据 启动阶段启动时间(…...

ArcGis将同一图层的多个面要素合并为一个面要素

这里写自定义目录标题 1.加载面要素的shp数据 2.点击菜单栏的地理处理–融合,如下所示: 3.将shp面要素输入,并设置输出,点击确定即可合并。合并后的属性表就只有一个数据了。...

PHP和Node.js哪个更爽?

先说结论,rust完胜。 php:laravel,swoole,webman,最开始在苏宁的时候写了几年php,当时觉得php真的是世界上最好的语言,因为当初活在舒适圈里,不愿意跳出来,就好比当初活在…...

在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…...

【JavaSE】多线程基础学习笔记

多线程基础 -线程相关概念 程序(Program) 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序,比如我们使用QQ,就启动了一个进程,操作系统就会为该进程分配内存…...

(一)单例模式

一、前言 单例模式属于六大创建型模式,即在软件设计过程中,主要关注创建对象的结果,并不关心创建对象的过程及细节。创建型设计模式将类对象的实例化过程进行抽象化接口设计,从而隐藏了类对象的实例是如何被创建的,封装了软件系统使用的具体对象类型。 六大创建型模式包括…...

关于uniapp展示PDF的解决方案

在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项&#xff1a; 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库&#xff1a; npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...

Python 训练营打卡 Day 47

注意力热力图可视化 在day 46代码的基础上&#xff0c;对比不同卷积层热力图可视化的结果 import torch import torch.nn as nn import torch.optim as optim from torchvision import datasets, transforms from torch.utils.data import DataLoader import matplotlib.pypl…...

二维FDTD算法仿真

二维FDTD算法仿真&#xff0c;并带完全匹配层&#xff0c;输入波形为高斯波、平面波 FDTD_二维/FDTD.zip , 6075 FDTD_二维/FDTD_31.m , 1029 FDTD_二维/FDTD_32.m , 2806 FDTD_二维/FDTD_33.m , 3782 FDTD_二维/FDTD_34.m , 4182 FDTD_二维/FDTD_35.m , 4793...

门静脉高压——表现

一、门静脉高压表现 00:01 1. 门静脉构成 00:13 组成结构&#xff1a;由肠系膜上静脉和脾静脉汇合构成&#xff0c;是肝脏血液供应的主要来源。淤血后果&#xff1a;门静脉淤血会同时导致脾静脉和肠系膜上静脉淤血&#xff0c;引发后续系列症状。 2. 脾大和脾功能亢进 00:46 …...

高效的后台管理系统——可进行二次开发

随着互联网技术的迅猛发展&#xff0c;企业的数字化管理变得愈加重要。后台管理系统作为数据存储与业务管理的核心&#xff0c;成为了现代企业不可或缺的一部分。今天我们要介绍的是一款名为 若依后台管理框架 的系统&#xff0c;它不仅支持跨平台应用&#xff0c;还能提供丰富…...

iOS 项目怎么构建稳定性保障机制?一次系统性防错经验分享(含 KeyMob 工具应用)

崩溃、内存飙升、后台任务未释放、页面卡顿、日志丢失——稳定性问题&#xff0c;不一定会立刻崩&#xff0c;但一旦积累&#xff0c;就是“上线后救不回来的代价”。 稳定性保障不是某个工具的功能&#xff0c;而是一套贯穿开发、测试、上线全流程的“观测分析防范”机制。 …...