二刷力扣--链表
链表
链表类型:
单链表(可以访问后面的一个节点)
双链表(可以访问前后节点)
循环链表(最后一个节点指向首节点)
在Python中定义单链表节点:
class ListNode:def __init__(self, val, next=None):self.val = valself.next = next
移除链表元素 203.
#链表删除 #哑节点
给你一个链表的头节点 head
和一个整数 val
,请你删除链表中所有满足 Node.val == val
的节点,并返回 新的头节点 。
为了统一处理删除操作,在head节点前添加一个哑节点。
class Solution:def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:dummy = ListNode(0, head)pre = dummycur = dummy.nextwhile cur:if cur.val == val:pre.next = cur.next cur = cur.nextelse:pre = pre.nextcur = cur.nextreturn dummy.next
Python有垃圾回收,不需要手动删除节点。
设计链表 707.
你可以选择使用单链表或者双链表,设计并实现自己的链表。
单链表中的节点应该具备两个属性:val
和 next
。val
是当前节点的值,next
是指向下一个节点的指针/引用。
class Node:def __init__(self, val=0, next=None):self.val = valself.next = nextclass MyLinkedList:def __init__(self):self.dummy = Node(-1, None)self.max_index = -1 def get(self, index: int) -> int:if index < 0 or index > self.max_index:return -1cur = self.dummy.next for i in range(index):cur = cur.nextreturn cur.valdef addAtHead(self, val: int) -> None:self.dummy.next = Node(val, self.dummy.next)self.max_index += 1def addAtTail(self, val: int) -> None:cur = self.dummywhile cur.next:cur = cur.nextcur.next = Node(val)self.max_index += 1def addAtIndex(self, index: int, val: int) -> None:if index < 0 or index > self.max_index + 1:return cur = self.dummyi = 0for i in range(index):cur = cur.nextcur.next = Node(val, cur.next)self.max_index += 1def deleteAtIndex(self, index: int) -> None:if index < 0 or index > self.max_index:return cur = self.dummyfor i in range(index):cur = cur.nextcur.next = cur.next.next self.max_index -= 1
反转链表 206.
给你单链表的头节点 head
,请你反转链表,并返回反转后的链表。
#双指针
使用temp保存cur.next ,因为反转后cur.next就改变了,无法再访问原来的下一个元素了。
class Solution:def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:pre = Nonecur = headwhile cur:temp = cur.next # 下一个节点cur.next = pre # 反转next方向pre = curcur = temp # 去下一个return pre
两两交换链表中的节点 24.
#哑节点
给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。
有些题解里很多cur.next.next.next,看起来很麻烦。 用临时节点记录一下似乎就不用那么多next了。而且也不用考虑.next赋值的顺序了。
class Solution:def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:dummy = ListNode(0, head)cur = dummy# 交换cur后面的两个节点while cur.next and cur.next.next:node1 = cur.next node2 = node1.next node3 = node2.next # cur->node1->node2-->node3(node2.next) ----> cur->node2->node1-->node3(node2.next) cur.next = node2 node2.next = node1 node1.next = node3cur = node1 return dummy.next
删除链表的倒数第N个节点 19.
#双指针 #哑节点
双指针的应用。快指针fast先走n步,当快指针到达倒数第1个节点时,慢指针slow到达倒数n+1个节点,删除slow的下一个节点。
哑节点对简化删除操作很有用,如果不用哑节点,删除head就要特殊处理。
class Solution:def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:dummy = ListNode(0, head)fast = dummyslow = dummy# 当fast 到达倒数第1个节点, slow到达倒数第n+1个节点for i in range(n):fast = fast.nextwhile fast.next :fast = fast.nextslow = slow.nextslow.next = slow.next.next return dummy.next
链表相交 面试题 02.07. 同 160
#双指针
给你两个单链表的头节点 headA
和 headB
,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null
。
两个链表如果有相同的节点,则从相同节点开始,一直到末尾都是相同的。
让较长的链表先走 abs(lengthA-lengthB)个节点,然后比较两个链表。
class Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:def getLength(head):length = 0while head:head = head.nextlength += 1return lengthlengthA = getLength(headA)lengthB = getLength(headB) Long, Short = (headA, headB) if lengthA > lengthB else (headB, headA)for _ in range (abs(lengthA- lengthB)):Long = Long.nextwhile Short:if Short == Long:return Shortelse:Short = Short.nextLong = Long.nextreturn None
环形链表II 142.
#集合 #双指针
- 直接用
set
记录访问过的节点,再次遇到则表明出现了环。
class Solution:def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:visited = set()pos = headwhile pos:if pos in visited:return poselse:visited.add(pos)pos = pos.nextreturn None
- 双指针。快指针fast一次走两步,慢指针slow一次走一步。如果有环,两个指针一定会遇到。
而找到环的入口比较难,需要推导一下。(这个不太好理解,推荐看代码随想录的视频)
相遇时,slow指针走过的节点数是 x+y, fast走过的节点数是 x+y+ n(y+z) ,n>=1
fast一次走两个节点,所以走过的节点数是slow的两倍,即 x+y+n(y+z) = 2(x+y)。 化简一下,得到 x = (n-1)(y+z) + z
n = 1时, x = z 也就是说,一个指针index1从slow与fast相遇点出发,一个指针index2从头节点出发,会在入口节点相遇。
n大于1时和n为1的时候 效果是一样的,一样可以通过这个方法找到 环形的入口节点,只不过,index1 指针在环里 多转了(n-1)圈,然后再遇到index2,相遇点依然是环形的入口节点
class Solution:def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:fast = headslow = headwhile fast and fast.next:slow = slow.nextfast = fast.next.nextif slow == fast:index1 = fastindex2 = headwhile index1 != index2:index1 = index1.nextindex2 = index2.nextreturn index2return None
链表小结
哑节点对简化链表操作很有用。添加一个哑节点,对头节点的处理会和其他节点一样。
双指针是常用的方法,可以用来判断链表是否有环,找到链表倒数第n个元素。
相关文章:
二刷力扣--链表
链表 链表类型: 单链表(可以访问后面的一个节点) 双链表(可以访问前后节点) 循环链表(最后一个节点指向首节点) 在Python中定义单链表节点: class ListNode:def __init__(self, v…...
返回值加const ,为了不拷贝得到成员的值,但被赋值的左值也要const
1. getA 函数返回值 什么都不加,也改不了c里面a的指针指向 why?返回成员变量时,会复制一下。 返回成员变量时,一般会赋值一下没有RVO_地摊书贩的博客-CSDN博客 2. getA 函数返回值 加了引用, 就没有复制 3. getA 函数…...
本地如何使用HTTPS进行调试
在现代前端开发中,HTTPS已经成为不可或缺的一部分,因为它在保护用户数据和确保网站安全性方面发挥着关键作用。然而,有时在本地开发过程中启用HTTPS可能会变得有些复杂。在本文中,我们将介绍如何轻松地在本地进行HTTPS调试&#x…...
观察者模式:对象之间的订阅机制
欢迎来到设计模式系列的第十三篇文章!在之前的文章中,我们学习了许多常用的设计模式,今天我们将介绍观察者模式,它是一种行为型设计模式,用于定义对象之间的一对多依赖关系,当一个对象的状态发生变化时&…...
【1462. 课程表 IV】
来源:力扣(LeetCode) 描述: 你总共需要上 numCourses 门课,课程编号依次为 0 到 numCourses-1 。你会得到一个数组 prerequisite ,其中 prerequisites[i] [ai, bi] 表示如果你想选 bi 课程,你…...
Kerberos 身份验证
简介 Kerberos 是一种由 MIT(麻省理工大学)提出的一种基于加密 Ticket 的身份认证协议。它旨在通过使用密钥加密技术为客户端/服务器应用程序提供强身份验证,用于验证用户或主机的标识。。 适用范围:Windows Server 2022、Window…...
R语言贝叶斯METROPOLIS-HASTINGS GIBBS 吉布斯采样器估计变点指数分布分析泊松过程车站等待时间...
原文链接:http://tecdat.cn/?p26578 指数分布是泊松过程中事件之间时间的概率分布,因此它用于预测到下一个事件的等待时间,例如,您需要在公共汽车站等待的时间,直到下一班车到了(点击文末“阅读原文”获取…...
通付盾入选2023年度“上市苗圃工程”重点企业
近日,2023年度苏州工业园区企业上市苗圃工程认定名单公示,江苏通付盾科技有限公司成功入选园区“上市苗圃工程”重点企业。 2023年第一批次苗圃企业认定结果: 企业上市苗圃工程 上市企业是衡量地方综合经济实力的重要标尺,也是区…...
SpringMVC之文件上传下载
SpringMVC是一个基于Java的Web框架,它提供了一套用于构建Web应用程序的开发模型。在SpringMVC中,文件上传和下载是常见的功能之一。 SpringMVC文件上传和下载的介绍: 介绍文件上传: 在SpringMVC中,文件上传功能可以通…...
嵌入式IDE(2):KEIL中SCF分散加载链接文件详解和实例分析
在上一篇文章IAR中ICF链接文件详解和实例分析中,我通过I.MX RT1170的SDK中的内存映射关系,分析了IAR中的ICF链接文件的语法。对于MCU编程所使用的IDE来说,IAR和Keil用得比较多,所以这一篇文章就来分析一下Keil的分散文件.scf(scat…...
Linux防火墙常用操作及端口开放
Linux防火墙常用操作及端口开放 1.查看防火墙状态 firewall-cmd --state 2.开启防火墙 systemctl start firewalld.service 3.开启指定端口 firewall-cmd --zonepublic --add-port3306/tcp --permanent firewall-cmd --zonepublic --add-port6379/tcp --permanent 显示success表…...
[JAVAee]Linux上的javax.mail报错
我们把在window写的项目部署到Linux上的Tomcat时,如果发现使用不了了,该如何找到错误呢?找到报错的地方在哪呢? 在Linux环境下来到Tomcat目录下的logs目录,输入: tail -f catalina.out -n 500 tail 就是把文件的末尾几行读取到终端上,并会持续刷新 -f 循环读取 catalina.ou…...
开学季|校园迎新哪家强?VR全景来导航
九月开学迎新季,各大高校的迎新活动开展的如火如荼,随着科技的不断进步,高校为了更好的开展迎新活动,让新生们尽快熟悉新的校园和生活,会利用VR全景技术带领着新生进行校园游览,给予新生们巨大便利的同时&a…...
el-checkbox-group限制勾选数量
<!--* Description: 视频监控 页面* Author: mhf* Date: 2023-08-15 13:26:33 --> <template><div class"videoSurveillance"><el-row :gutter"24"><el-col :span"4"><div class"videoSurveillance-left&…...
【JavaScript】WebAPI入门到实战
文章目录 一、WebAPI背景知识1. 什么是WebAPI?2. 什么是API? 二、DOM基本概念三、获取元素三、事件初识1. 点击事件2. 键盘事件 四、操作元素1. 获取/修改元素内容2. 获取/修改元素属性3. 获取/修改表单元素属性4. 获取/修改样式属性 五、操作节点1. 新增…...
奥康的高尔夫鞋,圈不住投资者的心
文 | 螳螂观察 作者 | 青月 鞋服行业终于熬过了“寒冬”,2023年行业景气度开始逐步回暖。 东方财富Choice数据显示,截至8月17日,已有28家鞋帽服装类上市公司发布了2023年中期业绩预告或快报,其中,9家预增࿰…...
vue2配置环境变量并且nginx运行成功
需求:我在vue项目配置了生产环境和开发环境,之后通过proxy代理的方式把地址转发到真实的服务器地址上用于请求接口,之后把项目打包后上传到nginx上,之后接口报错404,但是本地运行是可以访问的,找了很久终于…...
Java+Swing形成GUI图像界面
一、Swing 简介 Swing 主要用来开发 GUI 程序,GUI(Graphical User Interface)即图形用户界面。Java 中针对 GUI 设计提供了丰富的类库,这些类分别位于 java.awt 和 java.swing 中,简称 AWT 和 Swing ;其中,AWT(Abstract Window Toolkit)是抽象窗口工具包,是 Java 平…...
编辑距离 -- 动规
72. 编辑距离 给出动规的两种常见实现形式:自顶向下、自底向上,前者一般借助递归函数备忘录实现,后者通常基于dp数组实现。 class MinDistance:"""72. 编辑距离https://leetcode.cn/problems/edit-distance/""&quo…...
douyin【商品抢购js脚本】
文章目录 前言订阅须知知识点源码前言 脚本主要用来实现抢购douyin商城、直播间秒杀商品等一系列商品 订阅须知 订阅后,只提供js源代码,不提供教学,请根据源码自行抓包知识点 1、在查询串插入一个固定的键rstr 2、对查询串进行按键排序并取值,对空格和+进行转义为a …...
常见Web安全技术总结!474页Web安全从入门到精通(附PDF)
Web安全范围比较大,知识点比较杂,很多朋友都无从下手,这不可怕,可怕的是乱下手,其实往往基础才是决定你是否能走远的关键。 为了帮助大家入门网安,给大家推荐一份《新手Web安全入门到精通》,共…...
Prometheus 监控指南:如何可靠地记录数字时间序列数据
🌷🍁 博主猫头虎(🐅🐾)带您 Go to New World✨🍁 🐅🐾猫头虎建议程序员必备技术栈一览表📖: 🛠️ 全栈技术 Full Stack: 📚…...
rsync远程同步+inotify监控
目录 一、Rsync 简介 1、rsync是什么 2、备份的方式 3、rsync同步方式 4、常用rsync命令 5、配置源的两种表达方法 二、rsync实验 1、本地复制 编辑编辑 2、异地复制 2.1 rsync服务器配置 2.2 rsync客户端配置 2.2.1 普通同步 2.2.2 免密同步 2.2.3 --delet…...
【面试经典150 | 数组】移除元素
文章目录 写在前面Tag题目来源题目解读解题思路方法一:原地操作 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章,欢迎催更…… 专栏内容以分析题目为主,并附带一些对于本题涉及到的数据结构等…...
玩转Mysql系列 - 第21篇:什么是索引?
这是Mysql系列第21篇。 本文开始连续3篇详解mysql索引: 第1篇来说说什么是索引? 第2篇详解Mysql中索引的原理 第3篇结合索引详解关键字explain 本文为索引第一篇:我们来了解一下什么是索引? 路人在搞计算机之前,…...
预处理指令
// The include directive instructs the preprocessor to paste the text of the given file into the current file. // 粘贴指定文件的内容 #include // 定义宏PI #define PI 3.1415926 // 取消定义PI #undef PI条件编译(Conditional Compilation) // 检查xxx是否已被定义为…...
强大的JTAG边界扫描(1):基本原理介绍
文章目录 1. 什么是边界扫描?2. JTAG硬件接口3. 边界扫描相关的软硬件4. 学习资料5. 总结 我是怎么了解到边界扫描的呢? 这就要从我淘到一块FPGA板卡的事情说起了。 前段时间我在某二手平台上淘了一块FPGA板子,它长这样: 板子的…...
【C++】源文件.cpp和头文件.h分离编程
优势介绍 将C代码分为头文件(.h)和源文件(.cpp)的做法有以下几个好处: 模块化和代码组织:将函数和类的声明(包括函数原型、类的成员和属性等)放在头文件中,将函数和类的…...
报错ssh: Could not resolve hostname
…按照网上好多教程试了一下: 新建密钥,添加到gitee,重新测试。修改host,加入gitee的ip地址到里面去。修改.gifconfig配置文件,配置成ssh的仓库链接。 这上面的方法都不行,后面发现一篇文章:SS…...
从零开始学网站建设:从需求分析到上线发布
从零开始学网站建设:从需求分析到上线发布 一、需求分析 在进行网站建设之前,首先需要与客户进行沟通,了解客户的需求和要求,并进行深入的分析和研究。根据不同的需求,需要确定网站的类型、功能、布局、风格等方面的…...
wordpress二级菜单排列/如何做一个网页
写在开头博主最近在升级博客插件时,测试添加评论会出现该错误。主要表现在升级到 PHP 7.1 之后,经常收到 A non-numeric value encountered 的 warning 信息。比如下面这段代码就会出现警告信息:$a 123a;$b b456;echo $a$b;解决方法A non-n…...
网站关键词可以做几个/企业邮箱哪个好
点击上方“蓝色字”可关注我们!暴走时评:日本交易所集团最近发布超级账本研究报告,对比目前主要的几种DLT方案,阐述该技术如何提高交易效率,以及该技术在金融服务中的可行性。作者提到秘密资产交易可能带来中心化和交易…...
南阳交友网站开发公司/舆情报告范文
2015年底的时候,到家集团启动了一个“凌云”项目,将所有系统从北京的M6机房迁移到阿里云,完成技术栈“上云”。项目涉及几百台机器,到家所有的业务,所有的系统,需要所有技术部门配合,耗时超过一…...
做网站具体流程步骤/软文范文
2.1 问题 本案例要求: 一共安装5台虚拟机 在所有机器中部署ES 启动服务查看验证集群状态 2.2 步骤 实现此案例需要按照如下步骤进行。 步骤一:安装elasticsearch和java-1.8.0-openjdk,同步配置文件 备注:在步骤一已经安装了一台…...
南宁网站建设公司哪家好/网站seo博客
框架搭建设想框架:在VS2010 下的项目管理流程RoadMarkingDetection:工程项目入口,启动项目,配置类型Configuration Type 为Application(.exe)可以调用以下所有模块(.lib)。commonClass:保存全局数据类、工具…...
宣讲家网站李慎明两学一做/百度一下你就知道原版
[Icons] Name: "{commondesktop}\{#MyAppName}"; Filename: "{app}\{#MyAppExeName}";IconFilename:{app}\{#MyAppExeName}; Tasks: desktopicon; Check: canAddIcon...