当前位置: 首页 > 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…...

Linux应用开发之网络套接字编程(实例篇)

服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案

随着新能源汽车的快速普及&#xff0c;充电桩作为核心配套设施&#xff0c;其安全性与可靠性备受关注。然而&#xff0c;在高温、高负荷运行环境下&#xff0c;充电桩的散热问题与消防安全隐患日益凸显&#xff0c;成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。

1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj&#xff0c;再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...

如何更改默认 Crontab 编辑器 ?

在 Linux 领域中&#xff0c;crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用&#xff0c;用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益&#xff0c;允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...

day36-多路IO复用

一、基本概念 &#xff08;服务器多客户端模型&#xff09; 定义&#xff1a;单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用&#xff1a;应用程序通常需要处理来自多条事件流中的事件&#xff0c;比如我现在用的电脑&#xff0c;需要同时处理键盘鼠标…...

为什么要创建 Vue 实例

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

Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐&#xff1a;「storms…...

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数据帧格式 📦 帧结构详解 🔍…...