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

算法通关村第二关|白银|链表反转拓展【持续更新】

1.指定区间反转

1.1 头插法:将区间内遍历到的结点插入到起始处之前。

public ListNode reverseBetween(ListNode head, int left, int right) {ListNode dummyNode = new ListNode(-1);dummyNode.next = head;ListNode pre = dummyNode;// 将pre移动到区间的前一位,pre.next指向每次遍历到的需要插入到起始处的结点for (int i = 0; i < left - 1; i++) {pre = pre.next;}// cur负责遍历ListNode cur = pre.next;// next存储遍历到的结点ListNode next;for (int i = 0; i < right - left; i++) {//存储遍历到的结点cur.nextnext = cur.next;//将cur.next向后移动,下次循环继续遍历cur.next = next.next;//让遍历到的结点指向起始处的结点next.next = pre.next;//pre指向新的起始处pre.next = next;}return dummyNode.next;
}

1.2 穿针引线法:找到需要裁切的地方,将子链表整体反转,然后再缝到切开的地方。

public ListNode reverseBetween(ListNode head, int left, int right){ListNode dummyNode = new ListNode(-1);dummyNode.next = head;ListNode pre = dummyNode;// 找 left 结点的前一个结点for (int i = 0; i < left - 1; i++) {pre = pre.next;}// 找 right 结点ListNode rightNode = pre;for (int i = 0; i < right - left + 1; i++) {rightNode = rightNode.next;}// 切割子链表ListNode leftNode = pre.next;ListNode succ = rightNode.next;rightNode.next = null;// 反转链表reverseList(leftNode);// 拼接pre.next = rightNode;leftNode.next = succ;return dummyNode.next;
}
// 反转链表算法
public ListNode reverseList(ListNode head) {ListNode prev = null;ListNode curr = head;while(curr != null){ListNode next = curr.next;// 这里对链表的结构进行了更改// 所以不需要返回值,但是上面的leftNode结构已经更改了curr.next = prev;prev = curr;curr = next;}return prev;}
}

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

捋清楚成对交换结点时的指针指向即可。

public ListNode swapPairs(ListNode head) {ListNode dummyHead = new ListNode(0);dummyHead.next = head;ListNode temp = dummyHead;while (temp.next != null && temp.next.next != null) {ListNode node1 = temp.next;ListNode node2 = temp.next.next;temp.next = node2;node1.next = node2.next;node2.next = node1;temp = node1;}return dummyHead.next;
}

3.单链表加1

3.1 基于栈实现。

public ListNode plusOne(ListNode head) {Stack<Integer> stack = new Stack();while (head != null) {stack.push(head.val);head = head.next;}int carry = 0;ListNode dummy = new ListNode(0);// 本题要加1,所以设置了adder为1int adder = 1;while (!stack.empty() || carry > 0) {int digit = stack.empty() ? 0 : stack.pop();int sum = digit + carry + adder;carry = sum / 10;sum = sum % 10;ListNode cur = new ListNode(sum);cur.next = dummy.next;dummy.next = cur;//加一次以后adder就可以置0了adder = 0;}return dummy.next;
}

3.2 链表反转实现。【持续更新】


4.链表加法

4.1 栈实现:栈顶都是两个数的最低位,所以可以一起弹出。

public ListNode addInListByStack(ListNode head1, listNode head2) {Stack<ListNode> stack1 = new Stack<>();Stack<ListNode> stack2 = new Stack<>();while (head1 != null) {stack1.push(head1);head1 = head1.next;}while (head2 != null) {stack2.push(head2);head2 = head2.next;}ListNode newHead = new ListNode(-1);int carry = 0;while (!stack1.empty() || !stack2.empty() || carry != 0) {ListNode a = new ListNode(0);ListNode b = new ListNode(0);if (!stack1.empty()) {a = stack1.pop();}if (!stack2.empty()) {b = stack2.pop();}int get_sum = a.val + b.val + carry;int ans = get_sum % 10;carry = get_sum / 10;ListNode cur = new ListNode(ans);cur.next = newHead.next;newHead.next = cur;}return newHead.next;
}

4.2 链表反转实现。

public class Solution {public ListNode addInList(ListNode head1, ListNode head2) {head1 = reverse(head1);head2 = reverse(head2);ListNode head = new ListNode(-1);ListNode cur = head;int carry = 0;while (head1 != null || head2 != null || carry != 0) {int sum = carry;if (head1 != null) {sum += head1.val;head1 = head1.next;}if (head2 != null) {sum != head2.val;head2 = head2.next;}cur.next = new ListNode(sum % 10);carry = sum / 10;cur = cur.next;}return reverse(head.next);}// 链表反转方法public ListNode reverse(ListNode head){ListNode cur = head;ListNode pre = null;while (cur != null) {ListNode temp = cur.next;cur.next = pre;pre = cur;cur = temp;}return pre;}
}

4.3 链表减法:【持续更新】。


5.再论链表的回文序列问题

书接上回,可以使用栈或者链表反转来做。

public boolean isPalindrome(ListNode head) {if (head == null || head.next == null) {return true;}ListNode slow = head, fast = head;ListNode pre = head, prepre = null;while (fast != null && fast.next != null) {pre = slow;slow = slow.next;fast = fast.next.next;pre.next = prepre;prepre = pre;}if (fast != null) {slow = slow.next;}while (pre != null && slow != null) {if (pre.val != slow.val) {return false;}pre = pre.next;slow = slow.next;}return true;
}

如果对您有帮助,请点赞关注支持我,谢谢!❤
如有错误或者不足之处,敬请指正!❤

相关文章:

算法通关村第二关|白银|链表反转拓展【持续更新】

1.指定区间反转 1.1 头插法&#xff1a;将区间内遍历到的结点插入到起始处之前。 public ListNode reverseBetween(ListNode head, int left, int right) {ListNode dummyNode new ListNode(-1);dummyNode.next head;ListNode pre dummyNode;// 将pre移动到区间的前一位&a…...

开发者职场“生存状态”大调研报告分析 - 第四版

听人劝、吃饱饭,奉劝各位小伙伴,不要订阅该文所属专栏。 作者:不渴望力量的哈士奇(哈哥),十余年工作经验, 跨域学习者,从事过全栈研发、产品经理等工作,现任研发部门 CTO 。荣誉:2022年度博客之星Top4、博客专家认证、全栈领域优质创作者、新星计划导师,“星荐官共赢计…...

代码与细节(一)

在用到 Java17的新特性 Unmodifiable Lists 时不知道你是否和我有同样的惊讶 为什么弄了这么多重载方法&#xff1f; 先说结论&#xff1a;为了性能。 其实一细想&#xff0c;都能想明白&#xff1a;varargs(可变参数) 的背后是数组的内存分配和初始化&#xff0c;相比正常的…...

AI绘画使用Stable Diffusion(SDXL)绘制中国古代神兽

一、引言 说到神奇异兽&#xff0c;脑海中首先就会跳出我国古代神话传说中的各种神兽。比如青龙、白虎、朱雀、玄武&#xff0c;再比如麒麟、凤凰、毕方、饕餮等等&#xff0c;这些都是大家耳熟能详的的神兽。 这些神兽不仅体现了人们丰富的创造力和想象力&#xff0c;更是我…...

老卫带你学---leetcode刷题(148. 排序链表)

148. 排序链表 问题&#xff1a; 给你链表的头结点 head &#xff0c;请将其按 升序 排列并返回 排序后的链表 。 示例 1&#xff1a;输入&#xff1a;head [4,2,1,3] 输出&#xff1a;[1,2,3,4]示例 2&#xff1a;输入&#xff1a;head [-1,5,3,4,0] 输出&#xff1a;[-1…...

21.1 stm32使用LTDC驱动LCD--配置说明

本文讲解如何配置LTDC驱动LCD的参数配置&#xff0c;以及CubeMx参数配置说明 本文使用的是淘宝买的一块带电容触摸的液晶显示屏&#xff1a;5寸TFT液晶显示屏高清800*480免驱40P通用RGBIPS全视角彩屏GT911 说实话&#xff0c;价格还是相对挺便宜的&#xff0c;值得入手&#xf…...

zabbix监控nginx的状态页面

zabbix监控nginx的状态页面 文章目录 zabbix监控nginx的状态页面1.环境说明2.所涉及到的知识点3.在nginx主机上安装zabbix_agent4.开启nginx状态显示页面5.进入zabbix的web页面配置主机&#xff0c;监控项&#xff0c;触发器5.1.添加主机5.2.创建监控项5.3.创建触发器 1.环境说…...

C语言初学者工具选择:vscode + MSYS2 + cmake 搭建 C环境

文章目录 前言1. MSYS2 安装1. 下载安装包2. 安装3. pacman 换清华大学源4. 安装 mingw-w64 toolchain 和 cmake ninja5. 将 toolchain 加入系统环境变量 2. 设置 vscode1. 必要的插件2. 一个简单的 vscode cmake 项目 最后C数据结构与算法CMake 前言 网上关于使用 vscode 配…...

【四:httpclient的使用】

目录 1、Demo案例2、请求一个带cookies的get请求3、请求一个带cookies的post请求案例一&#xff0c;案例二的properties的配置 1、Demo案例 public class MyHttpClient {Testpublic void test1() throws IOException {//用来存放我们的结果String result;HttpGet get new Htt…...

在innodb引擎中,count(*)、count(1)、count(主键)、count(字段)哪个性能最高?

在InnoDB引擎中&#xff0c;这四种计数值的效率高低取决于具体的数据库和数据表结构&#xff0c;无法一概而论哪个性能最高。不过&#xff0c;一般情况下可以按照以下顺序进行选择&#xff1a; count()&#xff1a;统计所有行的数量。由于InnoDB引擎的行锁是锁住整行&#xff…...

华为OD 跳格子2(200分)【java】B卷

华为OD统一考试A卷B卷 新题库说明 你收到的链接上面会标注A卷还是B卷。目前大部分收到的都是B卷。 B卷对应20022部分考题以及新出的题目&#xff0c;A卷对应的是新出的题目。 我将持续更新最新题目 获取更多免费题目可前往夸克网盘下载&#xff0c;请点击此链接进入&#xff1a…...

javascript/python 笔记: folium feature group自动切换

1 python部分 python部分只能是静态的结果 1.1 导入库 import folium import math 1.2 数据 cell_lst表示基站位置&#xff0c;location_lst表示 用户实际位置&#xff08;均为伪数据&#xff09; cell_lst[[1.341505, 103.682498],[1.342751, 103.679604],[1.341505, 10…...

Python中的元组

Python 元组 Python 的元组与列表类似&#xff0c;不同之处在于元组的元素不能修改。以下是关于Python元组的一些基本信息&#xff1a; 元组的使用&#xff1a;元组是一个不可变的序列类型&#xff0c;使用小括号 () 来定义。元组没有增加元素append、修改元素、删除元素pop的…...

在云计算环境中,如何利用 AI 改进云计算系统和数据库系统性能

文章目录 前言一、关于唐明洁教授二、AI for System2.1 面向分布式作业的人工智能2.1.1 现阶段企业云计算系统环境所遇到的普遍痛点2.1.2 云计算系统环境所遇到的普遍痛点的解决方案&#xff08;一&#xff09;Google Autopilot Eurosys 2021方案&#xff08;Pod级别&#xff0…...

OpenP2P实现内网穿透远程办公

OpenP2P是一个开源、免费、轻量级的P2P共享网络。你的设备将组成一个私有P2P网络&#xff0c;里面的设备可以直接访问其它成员&#xff0c;或者通过其它成员转发数据间接访问。如果私有网络无法完成通信&#xff0c;将会到公有P2P网络寻找共享节点协助通信。 相比BT网络用来共享…...

黑白棋(Othello, ACM/ICPC World Finals 1992, UVa220)rust解法

你的任务是模拟黑白棋游戏的进程。黑白棋的规则为&#xff1a;黑白双方轮流放棋子&#xff0c;每次必须让新放的棋子“夹住”至少一枚对方棋子&#xff0c;然后把所有被新放棋子“夹住”的对方棋子替换成己方棋子。一段连续&#xff08;横、竖或者斜向&#xff09;的同色棋子被…...

MySQL中如何进行表的优化和压缩?

在MySQL中&#xff0c;可以通过以下方式进行表的优化和压缩&#xff1a; 使用合适的存储引擎&#xff08;Storage Engine&#xff09;&#xff1a;MySQL提供了多种存储引擎&#xff0c;如InnoDB、MyISAM等。不同的存储引擎在表的优化和压缩方面有不同的特点。例如&#xff0c;I…...

【Java】Jsoup格式化html问题(文本空格折叠等)解决方法

问题说明 Jsoup格式化html文本时&#xff0c;如&#xff1a; Document document Jsoup.parse(html);这里在对html进行格式化的时候会将如下内容&#xff1a; <p> aaa </p>解析成如下格式&#xff1a; <p> aaa </p>即空格折叠问题&#xff…...

Ansible定义各类变量,引用变量方式介绍及注册变量和vars_prompt的用法示例

目录 一.Ansible定义变量 1.用途 2.定义规则 3.变量优先级 二.命令行定义变量 三.定义主机和主机组变量 1.主机变量 &#xff08;1&#xff09;内置主机变量 &#xff08;2&#xff09;简单示例 2.主机组变量 四.定义playbook变量 1.通过vars表示定义变量&#xff…...

各类证件的版面信息收集

香港身份证的版面分析&#xff1a; 证件页面&#xff1a; 相关的版面信息&#xff1a; 该页面包含香港身份证的信息&#xff0c;可以用于版面分析&#xff1b; 信息来源&#xff1a;香港不同证件说明大汇总|回乡证|居民身份证|护照|永居_手机网易网 台湾通行证号码&#xf…...

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

HBuilderX安装(uni-app和小程序开发)

下载HBuilderX 访问官方网站&#xff1a;https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本&#xff1a; Windows版&#xff08;推荐下载标准版&#xff09; Windows系统安装步骤 运行安装程序&#xff1a; 双击下载的.exe安装文件 如果出现安全提示&…...

现代密码学 | 椭圆曲线密码学—附py代码

Elliptic Curve Cryptography 椭圆曲线密码学&#xff08;ECC&#xff09;是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础&#xff0c;例如椭圆曲线数字签…...

三体问题详解

从物理学角度&#xff0c;三体问题之所以不稳定&#xff0c;是因为三个天体在万有引力作用下相互作用&#xff0c;形成一个非线性耦合系统。我们可以从牛顿经典力学出发&#xff0c;列出具体的运动方程&#xff0c;并说明为何这个系统本质上是混沌的&#xff0c;无法得到一般解…...

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...

Maven 概述、安装、配置、仓库、私服详解

目录 1、Maven 概述 1.1 Maven 的定义 1.2 Maven 解决的问题 1.3 Maven 的核心特性与优势 2、Maven 安装 2.1 下载 Maven 2.2 安装配置 Maven 2.3 测试安装 2.4 修改 Maven 本地仓库的默认路径 3、Maven 配置 3.1 配置本地仓库 3.2 配置 JDK 3.3 IDEA 配置本地 Ma…...

【Go语言基础【12】】指针:声明、取地址、解引用

文章目录 零、概述&#xff1a;指针 vs. 引用&#xff08;类比其他语言&#xff09;一、指针基础概念二、指针声明与初始化三、指针操作符1. &&#xff1a;取地址&#xff08;拿到内存地址&#xff09;2. *&#xff1a;解引用&#xff08;拿到值&#xff09; 四、空指针&am…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别

【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而&#xff0c;传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案&#xff0c;能够实现大范围覆盖并远程采集数据。尽管具备这些优势&#xf…...

为什么要创建 Vue 实例

核心原因:Vue 需要一个「控制中心」来驱动整个应用 你可以把 Vue 实例想象成你应用的**「大脑」或「引擎」。它负责协调模板、数据、逻辑和行为,将它们变成一个活的、可交互的应用**。没有这个实例,你的代码只是一堆静态的 HTML、JavaScript 变量和函数,无法「活」起来。 …...