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

代码随想录day04

24. 两两交换链表中的节点

● 力扣题目链接
● 给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。
● 你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

思路

● 使用迭代的方法,分析交换逻辑即可
○ 注意,可能链表节点个数奇数或偶数,分开讨论
○ 时间复杂度O(n) 空间复杂度O(1)
● 递归方法,时间复杂度O(n) 空间复杂度O(n)
○ 注意保存临时节点

代码

// 迭代
class Solution {public ListNode swapPairs(ListNode head) {if (head == null || head.next == null) return head; // 空或单个节点直接返回ListNode dummy = new ListNode(-1, head);ListNode pre = dummy;ListNode cur = head;ListNode temp;while (cur != null && cur.next != null) { // 节点个数可能为奇数或偶数temp = cur.next;pre.next = temp;cur.next = temp.next;temp.next = cur;pre = cur;cur = pre.next;}return dummy.next;}
}
// 递归
class Solution {public ListNode swapPairs(ListNode head) {if (head == null || head.next == null) return head;ListNode reHead = swapPairs(head.next.next);ListNode temp = head.next;temp.next = head;head.next = reHead;return temp;}
}

19.删除链表的倒数第N个节点

● 力扣题目链接
● 给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。

思路

● 双指针,快指针先走n步,然后快慢指针一起走,快指针到末尾,慢指针到要删除元素的前一个元素,删除即可
● 使用栈,空间复杂度为O(n) 先依次入栈,然后弹出n个元素,这时栈顶的正好是要删除节点的前一个节点,删除即可(注意虚拟头节点也入栈,不然删除头结点时会空指针)

代码

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(-1, head);ListNode f = dummy, s = dummy;while (n-- > 0) {f = f.next;}while (f.next != null) {f = f.next;s = s.next;}s.next = s.next.next;return dummy.next;}
}
// 使用栈
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {Deque<ListNode> stack = new ArrayDeque();ListNode dummy = new ListNode(-1, head);ListNode cur = dummy;while (cur != null) {stack.addFirst(cur);cur = cur.next;}for (int i = 0; i < n; i++) {stack.removeFirst();}ListNode pre = stack.peek();pre.next = pre.next.next;return dummy.next;}
}

面试题 02.07. 链表相交

● 力扣题目链接
● 给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null 。

思路

● 先求两个链表的长度,然后通过gap让两个链表尾部对齐,之后同时走,看会不会相遇,就是headA = headB
● 更快的方法,A和B同时遍历,走到空就从另一个链表头部继续遍历,如果相交就到相交节点,如果不相交就到空,时间复杂度O(m+n) 空间复杂度O(1)

代码

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {int lenA = getLen(headA);int lenB = getLen(headB);if (lenB > lenA) { // B长就交换长度和头结点int tempLen = lenA;lenA = lenB;lenB = tempLen;ListNode tempNode = headA;headA = headB;headB = tempNode;}int gap = lenA - lenB;while (gap-- > 0) { // 尾部对齐headA = headA.next;}while (headA != null) {if (headA == headB) return headA;headA = headA.next;headB = headB.next;}return null;}// 求链表长度private int getLen(ListNode head) {int len = 0;while (head != null) {len++;head = head.next;}return len;}
}public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode tA = headA;ListNode tB = headB;while (tA != tB) {tA = tA != null ? tA.next : headB;tB = tB != null ? tB.next : headA;}return tA;}
}

142.环形链表II

● 力扣题目链接
● 题意: 给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
● 为了表示给定链表中的环,使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

思路

● 快慢指针处理即可

代码

public class Solution {public ListNode detectCycle(ListNode head) {ListNode f = head, s = head;while (f != null && f.next != null) { // 快指针一次走两步,注意判空f = f.next.next;s = s.next;if (f == s) { // 相遇,有环f = head; // 快指针回到头结点while (f != s) {f = f.next;s = s.next; // 一起向前走}return f; // 找到入环节点}}return null; // 没有环,返回null}
}

相关文章:

代码随想录day04

24. 两两交换链表中的节点 ● 力扣题目链接 ● 给定一个链表&#xff0c;两两交换其中相邻的节点&#xff0c;并返回交换后的链表。 ● 你不能只是单纯的改变节点内部的值&#xff0c;而是需要实际的进行节点交换。 思路 ● 使用迭代的方法&#xff0c;分析交换逻辑即可 ○ …...

[Realtek] WPA_SUPPLICANT + WPA_CLI使用指南

开启wpa_supplicant wpa_supplicant –Dnl80211 -iwlan0 -c ./wpa.conf –B 或者 wpa_supplicant -Dwext -iwlan0 -c ./wpa.conf -B 扫描AP wpa_cli -p/var/run/wpa_supplicant scan 查看AP扫描结果 wpa_cli -p/var/run/wpa_supplicant scan_results 连接到热点 OPEN…...

# ⛳ Docker 安装、配置和详细使用教程-Win10专业版

目录 ⛳ Docker 安装、配置和详细使用教程-Win10专业版&#x1f69c; 一、win10 系统配置&#x1f3a8; 二、Docker下载和安装&#x1f3ed; 三、Docker配置&#x1f389; 四、Docker入门使用 ⛳ Docker 安装、配置和详细使用教程-Win10专业版 &#x1f69c; 一、win10 系统配…...

Linux 教程

目录 Linux 教程 内核引导 运行init 运行级别 系统初始化 Linux 系统目录结构 Linux 教程 Lin...

图论——最短路算法

引入&#xff1a; 如上图&#xff0c;已知图G。 问节点1到节点3的最短距离。 可心算而出为d[1,2]d[2,3]112,比d[1,3]要小。 求最短路径算法&#xff1a; 1.Floyd(弗洛伊德) 是一种基于三角形不等式的多源最短路径算法。边权可以为负数 表现为a[i,j]a[j,k]<a[i,k]。 …...

在项目中增加网络加载需要考虑什么?

1、下载器 网络加载的第一步肯定是下载&#xff0c;那么选择一个合适的下载器是十分重要的&#xff0c;这个下载器最好支持什么功能&#xff1f; 多线程下载&#xff08;同时需要服务端支持&#xff0c;下载时可指定range&#xff09; 断点续传 通用性&#xff08;其他位置也…...

阿里云服务器部署RabbitMQ流程

阿里云百科分享使用阿里云服务器部署RabbitMQ流程&#xff0c;RabbitMQ是实现了高级消息队列协议&#xff08;AMQP&#xff09;的开源消息代理软件&#xff0c;用于在分布式系统中存储转发消息&#xff0c;有良好的易用性、扩展性和高可用性。本文介绍如何通过ECS实例部署Rabbi…...

青大数据结构【2014】

一、单选 二、简答 为了解决顺序队列的假溢出问题&#xff0c;提出了循环队列&#xff0c;即把存储队列的表从逻辑上看成一个环 判别队列空和满有三种方法&#xff1a; 1&#xff09;采用计数器判别&#xff0c;空时&#xff0c;计数器为0&#xff1b;满时&#xff0c;计数器…...

Ansible Playbook快速部署一主多从MySQL集群

部署目标&#xff1a; 1、快速部署一套一主两从的mysql集群 2、部署过程中支持交互式定义安装目录及监听端口号 部署清单目录结构&#xff1a; rootmaster:/opt/mysql# tree . . ├── group_vars │ └── all.yml ├── hosts ├── mysql.yml └── roles└── mys…...

27.Netty源码之FastThreadLocal

highlight: arduino-light FastThreadLocal FastThreadLocal 的实现与 ThreadLocal 非常类似&#xff0c;Netty 为 FastThreadLocal 量身打造了 FastThreadLocalThread 和 InternalThreadLocalMap 两个重要的类。下面我们看下这两个类是如何实现的。 FastThreadLocalThread 是对…...

linux下离线安装docker

linux下离线安装docker 一、安装docker Docker 官网离线安装文档 https://docs.docker.com/engine/install/binaries/ 整理步骤如下&#xff1a; 官网下载 docker 安装包&#xff0c;地址为 https://download.docker.com/linux/static/stable/&#xff0c;如果是x86就选择x…...

SQL server 异地备份数据库

异地备份数据库 1.备份服务器中设置共享文件夹 2.源服务器数据库中添加异地备份代理作业 EXEC sp_configure show advanced options, 1;RECONFIGURE; EXEC sp_configure xp_cmdshell, 1;RECONFIGURE; declare machine nvarchar(50) 192.168.11.10 --服务器IP declare pa…...

高并发系统设计要点

在系统设计时&#xff0c;如果能预先看到一些问题&#xff0c;并在设计层面提前解决&#xff0c;就会给后期的开发带来很大的便捷。相反&#xff0c;有缺陷的架构设计可能会导致后期的开发工作十分艰难&#xff0c;甚至会造成“推倒重来”的情形。因此&#xff0c;在系统设计阶…...

Redis 拒绝服务漏洞(CVE-2023-28856)修复处理

一、漏洞描述 Redis Labs Redis是美国Redis Labs公司的一套开源的使用ANSI C编写、支持网络、可基于内存亦可持久化的日志型、键值&#xff08;Key-Value&#xff09;存储数据库&#xff0c;并提供多种语言的API。 Redis 7.0.0 到 7.0.10版本、6.2.0 到 6.2.11版本、6.0.0 到 …...

Android保存网页的方法

首先要使用js交互就需要懂原理&#xff1a; 感谢大佬&#xff1a;js中document节点获取页面元素的六种方式 1.querySelector()方法 描述&#xff1a;本方法用于根据给定的选择器选中页面元素 如果有多个元素满足条件&#xff0c;则返回第一个满足条件的元素节点 语法&#xff…...

P2P 网络,PING程序。

没有废话,直接上版本号和代码,以及讲解。 crate版本号libp2p0.52.1tokio1.30.0依赖配置: [dependencies] tokio = { version="1.30.0", features=["full"] } libp2p = { version="0.52.1", features=["tokio","dns", &q…...

OPENCV C++(十二)模板匹配

正常模板匹配函数 matchTemplate(img, templatee, resultMat, 0);//模板匹配 这里0代表的是方法&#xff0c;一般默认为0就ok img是输入图像 templatee是模板 resultmat是输出 1、cv::TM_SQDIFF&#xff1a;该方法使用平方差进行匹配&#xff0c;因此最佳的匹配结果在结果为…...

【配置环境】Linux下安装MySQL

目录 一&#xff0c;环境 二&#xff0c;安装步骤 1.使用包管理器安装MySQL 2.配置MySQL的安全选项 3.设置root用户使用密码进行身份验证&#xff08;可选&#xff09; 三&#xff0c;拓展知识 1.如何修改MySQL的密码策略&#xff1f; 一&#xff0c;环境 VMware Workst…...

【100天精通python】Day30:使用python操作数据库_数据库基础入门

专栏导读 专栏订阅地址&#xff1a;https://blog.csdn.net/qq_35831906/category_12375510.html 1 数据库基础知识介绍 1.1 什么是数据库&#xff1f; 数据库是一个结构化存储和组织数据的集合&#xff0c;它可以被有效地访问、管理和更新。数据库的目的是为了提供一种可靠的…...

android 如何分析应用的内存(十八)终章——使用Perfetto查看内存与调用栈之间的泄露

android 如何分析应用的内存&#xff08;十八&#xff09; 在前面两篇文章中&#xff0c;先是介绍了如何用AS查看Android的堆内存&#xff0c;然后介绍了使用MAT查看 Android的堆内存。AS能够满足基本的内存分析需求&#xff0c;但是无法进行多个堆的综合比较&#xff0c;因此…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

Caliper 配置文件解析:config.yaml

Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...

【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)

1.获取 authorizationCode&#xff1a; 2.利用 authorizationCode 获取 accessToken&#xff1a;文档中心 3.获取手机&#xff1a;文档中心 4.获取昵称头像&#xff1a;文档中心 首先创建 request 若要获取手机号&#xff0c;scope必填 phone&#xff0c;permissions 必填 …...

力扣-35.搜索插入位置

题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...

Selenium常用函数介绍

目录 一&#xff0c;元素定位 1.1 cssSeector 1.2 xpath 二&#xff0c;操作测试对象 三&#xff0c;窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四&#xff0c;弹窗 五&#xff0c;等待 六&#xff0c;导航 七&#xff0c;文件上传 …...

多模态图像修复系统:基于深度学习的图片修复实现

多模态图像修复系统:基于深度学习的图片修复实现 1. 系统概述 本系统使用多模态大模型(Stable Diffusion Inpainting)实现图像修复功能,结合文本描述和图片输入,对指定区域进行内容修复。系统包含完整的数据处理、模型训练、推理部署流程。 import torch import numpy …...

Modbus RTU与Modbus TCP详解指南

目录 1. Modbus协议基础 1.1 什么是Modbus? 1.2 Modbus协议历史 1.3 Modbus协议族 1.4 Modbus通信模型 🎭 主从架构 🔄 请求响应模式 2. Modbus RTU详解 2.1 RTU是什么? 2.2 RTU物理层 🔌 连接方式 ⚡ 通信参数 2.3 RTU数据帧格式 📦 帧结构详解 🔍…...

VisualXML全新升级 | 新增数据库编辑功能

VisualXML是一个功能强大的网络总线设计工具&#xff0c;专注于简化汽车电子系统中复杂的网络数据设计操作。它支持多种主流总线网络格式的数据编辑&#xff08;如DBC、LDF、ARXML、HEX等&#xff09;&#xff0c;并能够基于Excel表格的方式生成和转换多种数据库文件。由此&…...