怎么做网站在线客服/seog
2.链表
2.1判断是否是回文链表
1.方法一:利用栈反转链表
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public boolean isPalindrome(ListNode head) {Stack<ListNode> listNodes = new Stack<>();ListNode p = head;//利用栈反转链表,判断是否是回文链表while (p != null) {//将链表中所有元素入栈listNodes.push(p);p = p.next;}while (!listNodes.empty()) {if (listNodes.pop().val == head.val) {//head = head.next;} else {return false;}}return true;}
}
2.方法2:利用快慢指针
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public boolean isPalindrome(ListNode head) {//代表快指针,一次走两步ListNode fast = head;//代表慢指针,一次走一步ListNode slow = head;while (fast.next != null && fast.next.next != null) {fast = fast.next.next;slow = slow.next;}//退出循环时,如果链表节点是奇数个,快指针在尾节点,慢指针在中点。如果是偶数个,快指针还是在尾节点,慢指针在中点前一个。//把右半部分链表反转slow = reverseList(slow.next);while (slow != null) {if (head.val != slow.val) return false;//值不相同,直接返回falsehead = head.next;slow = slow.next;}return true;}//反转链表public static ListNode reverseList(ListNode head) {ListNode cur = head;ListNode pre = null;while (cur != null) {ListNode temp = cur.next;cur.next = pre;pre = cur;cur = temp;}return pre;}
}
2.2 模板题:反转链表
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseList(ListNode head) {//cur:用于遍历链表元素的指针,代表当前遍历到的节点,初始化当然为head了ListNode cur = head;//pre:代表当前cur节点,反转后应该指向的节点。因为cur初始在head,反转以后就是尾节点了指向null,所以pre初始化为nullListNode pre = null;while(cur != null){//当元素还没遍历完的时候//在cur指向pre前,用于保存cur.next,防止链表找不到了。ListNode temp = cur.next;//让当前节点cur,指向precur.next = pre;//让pre变为反转链表的最前面一个节点pre = cur;//让cur移动到原链表的头节点cur = temp;}// 注意:pre的含义还是反转链表的头节点!return pre;}
}
复杂度分析:
时间复杂度 O(N)O(N)O(N) : 遍历链表使用线性大小时间。
空间复杂度 O(1)O(1)O(1) : 变量 pre 和 cur 使用常数大小额外空间。
已经是最优的解法了,还有一种递归方法就不赘述了。
2.3 分割链表(将链表分为小于某个值,等于某个值,大于某个值)
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode partition(ListNode head, int x) {
if (head == null || head.next == null) return head;//代表小于目标值区域的头和尾ListNode h1 = null;ListNode t1 = null;//代表大于等于目标值的头和尾ListNode h2 = null;ListNode t2 = null;//用于保存head的下一个节点//注意:这里最后拼接好了以后,小于区域的头就是整个链表的新的头节点,因此,head可以作为遍历链表的指针。ListNode next = head.next;while (head != null) {//遍历next = head.next;head.next = null;if (head.val < x) {//如果当前节点的val小于目标值if (h1 == null) {//如果当前节点是小于区域的第一个节点h1 = head;t1 = head;} else {t1.next = head;t1 = head;}} else {if (h2 == null) {//如果当前节点是大于区域的第一个节点h2 = head;t2 = head;} else {//其他情况就把该节点尾插法插入链表中t2.next = head;t2 = head;}}head = next;}//进行小于区域链表和大于等于区域链表的拼接if (h2 == null) {//如果没有大于等于区域return h1;}if (h1 == null) {//如果没有小于区域return h2;}//如果两种区域都有,则让小于区域的尾指针指向大于等于区域的头指针t1.next = h2;return h1;}
}
2.4 随机链表的赋值
/*
// Definition for a Node.
class Node {int val;Node next;Node random;public Node(int val) {this.val = val;this.next = null;this.random = null;}
}
*/class Solution {public Node copyRandomList(Node head) {//创建一个map,key为老链表的节点。val为新链表的节点HashMap<Node,Node> map = new HashMap<Node,Node>();Node cur = head;//遍历链表,设置map的key和valuewhile(cur != null){map.put(cur,new Node(cur.val));cur = cur.next;}cur = head;//再次遍历老链表,给新链表设置每一个节点的next和randomwhile(cur != null){//cur 老链表节点//map.get(cur) cur对应的新链表map.get(cur).next = map.get(cur.next);//设置新链表的nextmap.get(cur).random = map.get(cur.random);//设置新链表的randomcur = cur.next;}return map.get(head);}
}
2.5环形链表的判断
方法一:利用HashSet集合。
思路:遍历当前链表,每次遍历判断当前节点是否已经存在于set集合中。如果不存在,则把当前节点放入集合。如果已经存在,说明当前节点就是第一个入环节点。
/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val = x;* next = null;* }* }*/
public class Solution {public boolean hasCycle(ListNode head) {//创建一个set,用于存放链表中已经遍历了的节点HashSet<ListNode> set = new HashSet<>();while(head != null){//如果当前节点已经存在于set,说明存在环形结构if(set.contains(head)) return true;set.add(head);head = head.next;}return false;}
}
方法二:快慢指针
开始时,快慢指针都在头节点的位置。快指针一次走两步,慢指针一次走一步。
如果没有环结构,快指针一定先走到尾节点。
如果有环结构,快慢指针会在换里相遇。而相遇所要走的卷数不会大于两圈。
相遇以后,快指针/慢指针到头节点的位置。两个指针开始一次走一步。最终两个指针会在第一次入换节点相遇!(原理就不证明了)
/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val = x;* next = null;* }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {if(head == null || head.next == null || head.next.next == null) return null;//定义慢指针,一次走一步ListNode n1 = head.next;//定义快指针,一次走两步ListNode n2 = head.next.next;while(n1 != n2){//当n1 n2不相遇时循环,所以我开始时没有把两个指针都设置在头节点的位置if(n2.next == null || n2.next.next == null){//说明没有环结构,直接返回空return null;}n1 = n1.next;//慢指针一次走一步n2 = n2.next.next;//慢指针一次走两步}//快指针移到头节点,开始一次走一步n2 = head;while(n1 != n2){//当两个指针相遇时,就走到了第一个入环节点n1 = n1.next;n2 = n2.next;}return n1;}
}
2.6 链表相交
思路:两个单链表,如何判断有没有相交点呢?
1.先遍历两个链表,到尾节点时停止。如果这时候,两个链表的尾节点都不想等。说明二者不相交。
2.如果二者尾节点是同一个,则计算二者链表长度的差值。让长的链表先走差值个距离。然后,短的链表从头开始走,二者一定会在相交点相遇!
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) {* val = x;* next = null;* }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {//定义两个指针用于遍历两条链表ListNode cur1 = headA;ListNode cur2 = headB;int n = 0;//用于记录两条链表的差值while(cur1.next != null){cur1 = cur1.next;n++;}while(cur2.next != null){cur2 = cur2.next;n--;}if(cur1 != cur2){//尾节点都不想等,说明二者不相交return null;}//这样遍历完两条链表,n就是两条链表的长度差cur1 = n > 0 ? headA : headB;//让cur1指向两条链表中长的那一条cur2 = cur1 == headA ? headB : headA;//让cur2指向两条链表中短的那一条n = Math.abs(n);//n取绝对值while(n != 0){//让长的那条链表先移动两条链表差值的距离,再一起走,就会在相交部分汇合!cur1 = cur1.next;n--;}while(cur1 != cur2){cur1 = cur1.next;cur2 = cur2.next;}return cur1;}
}
2.7.两数相加
思路:
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode res = new ListNode();ListNode cur = res;int carry = 0;//当l1、l2中有一个不是空节点,或者还有进位,就继续循环while (l1 != null || l2 != null || carry != 0) {if (l1 != null) carry += l1.val;if (l2 != null) carry += l2.val;cur.next = new ListNode(carry % 10);//carry%10 就是该点的valcur = cur.next;carry = carry / 10;// carry/10 就是下一个点的进位if (l1 != null) l1 = l1.next;//l1 没有遍历完if (l2 != null) l2 = l2.next;}return res.next;}
}
2.8.合并两个有序链表
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode res = new ListNode();ListNode cur = res;while (list1 != null && list2 != null) {if (list1.val <= list2.val) {//如果l1链表的值更小cur = cur.next = list1;list1 = list1.next;} else {cur = cur.next = list2;list2 = list2.next;}}while (list1 != null) {//如果1还没遍历完cur = cur.next = list1;list1 = list1.next;}while (list2 != null) {//如果2还没遍历完cur = cur.next = list2;list2 = list2.next;}return res.next;}
}
2.9 反转链表2
题解参考:leetcode
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseBetween(ListNode head, int left, int right) {ListNode dummy = new ListNode(0, head);ListNode g = dummy;ListNode p = dummy;//g指向的下一个节点就是要开始反转的节点for (int i = 0; i < left - 1; i++) {g = g.next;p = p.next;}//p指向第left个节点p = p.next;for (int i = 0; i < right - left; i++) {ListNode temp = p.next;p.next = p.next.next;temp.next = g.next;g.next = temp;}return dummy.next;}
}
2.10.K个一组反转链表
本题思路和上一题差不多。举一反三,还是主要用g、p两个指针反转链表。
每组链表反转之前,g的next指向的都是待反转链表的第一个节点,p指向的就是待反转链表的第一个节点。
要注意的就是每次反转完链表p指针指向的就是反转后链表的最后一个元素,同时它的next也是下一组待反转链表的第一个元素,所以每次每组反转完以后,都要把p赋值给g。
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseKGroup(ListNode head, int k) {ListNode dummy = new ListNode(0, head);ListNode g = head;//计算一共有多少个节点,用来算要反转几组链表int count = 0;while (g != null) {g = g.next;count++;}g = dummy;ListNode p = g.next;//遍历for (int i = 0; i < count / k; i++) {p = g.next;//反转的每组链表for (int j = 1; j < k; j++) {ListNode temp = p.next;p.next = p.next.next;temp.next = g.next;g.next = temp;}//每组链表反转完,让cur的next指向下一组待反转链表第一个g = p;}return dummy.next;}
}
相关文章:

算法记录——链表
2.链表 2.1判断是否是回文链表 1.方法一:利用栈反转链表 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode…...

EasyExcel实现百万数据批量导出
当数据量比较大时,例如数据量达到百万级,传统的一次读取到内存中在写入excel文件的方法便不再适用了,可能会导致内存溢出;而且一次性将数据写入一张sheet工作表也不太好。 但我们可以选择数据分片的方式批量写入多个工作表。 测试…...

兆易GD32E508的SHRTIM配置 主从定时器 产生2对相位可调互补PWM 带死区
如有技术问题及技术需求请加作者微信! GD32E5系列MCU是基于Arm Cortex-M33处理器的32位通用微控制器。Cortex-M33处理器基于Armv8架构,处理器主频最高可达180MHz,支持强大的可扩展指令集,包括通用数据处理I/O控制任务、增强的数据处理位域操作、DSP和浮点运算器(FPU)。 GD…...

数据归组工具
利用C#将数据 [ {"name":"A","fzh":1}, {"name":"A","fzh":2}, {"name":"A","fzh":3}, {"name":"B","fzh":4}, {"name":"B",&…...

JavaScript 中的闭包的形成及使用场景
JavaScript 中的闭包 闭包(Closure) 是 JavaScript 中一个非常重要且独特的概念,它指的是 函数能够记住并访问其词法作用域内的变量,即使这个函数在其词法作用域之外执行。 通俗地说,闭包是 一个函数可以“记住”它在…...

后端返回内容有换行标识,前端如何识别换行
<br/>的话 用 v-html \n 可以用css样式 white-space: pre-wrap 后端返回结果 前端...

服务器被挂马,导致网站首页被更改怎么解决
当服务器被挂马并导致网站首页被篡改时,说明服务器或网站的安全性遭到破坏。为了修复并防止未来的攻击,你可以按照以下步骤进行操作: 1. 立即下线网站 目的:防止恶意软件进一步传播,保护用户数据和防止攻击者继续对网…...

Android 利用OSMdroid开发GIS
1、地址 Github地址:https://gitee.com/mirrors/osmdroid Git地址: GitCode - 全球开发者的开源社区,开源代码托管平台 Git下载包地址:Releases osmdroid/osmdroid GitHub 新建项目 osmdroid在线: (1)…...

一文上手skywalking【上】
一、skywalking预览 1.1 skywalking 概述 Apache SkyWalking, 适用于分布式系统的应用程序性能监控工具,专为微服务、云原生和基于容器的 (Kubernetes) 架构而设计。官方地址: https://skywalking.apache.org/ 适用于分布式系统的应用程…...

【JavaScript】JQuery基础知识及应用
一、JQuery的导入方法 https://editor.csdn.net/md/?articleId132214798 二、JQuery介绍 JQuery(JQ):JS的一个类库(方法库:包含了大量的、有助于项目开发的属性和方法) 第一代版本1.xx.xx: 1.11.3 兼容所有浏览器的࿰…...

初始爬虫9
1.元素定位后的操作 “find_element“仅仅能够获取元素,不能够直接获取其中的数据,如果需要获取数据需要使用以下方法”。下面列出了两个方法: 获取文本 element.text 通过定位获取的标签对象的 text 属性,获取文本内容 获取属性…...

从细胞到临床:表观组学分析技术在精准医疗中的角色
中国科学院等科研院所的顶尖人才发起,专注于多组学、互作组、生物医学等领域的研究与服务。在Nature等国际知名期刊发表多篇论文,提供实验整体打包、免费SCI论文润色等四大优势服务。在表观组学分析技术方面,提供DAP-seq、ATAC-seq、H3K4me3 …...

带你0到1之QT编程:二十、QT与MySQL喜结连理,构建数据库应用开发
此为QT编程的第二十谈!关注我,带你快速学习QT编程的学习路线! 每一篇的技术点都是很很重要!很重要!很重要!但不冗余! 我们通常采取总-分-总和生活化的讲解方式来阐述一个知识点! …...

梯度下降法及其性能评估
梯度下降法 梯度下降法是一种一阶迭代优化算法,用于寻找函数的局部最小值。在机器学习中,它通常用来最小化损失函数(也称为成本函数或误差函数),以提高模型对数据的拟合程度。梯度下降法的基本思想是沿着目标函数当前…...

906. 超级回文数
1. 题目 906. 超级回文数 2. 解题思路 题目意思很简单,在给定范围中找到所有满足,它本身是回文,且它的平方也是回文的数字个数。 这题需要注意题目给定的范围,后面很有用: 因为回文范围是有限的,那么我…...

代码随想录算法训练营||二叉树
前/中/后序遍历 递归方式 参考文章 题目 思路:其实递归方式的前中后序遍历的方式都差不多,区别是在父节点的遍历时间。 前序代码 class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result new…...

线上报名小程序怎么做
在这个数字化、智能化的时代,信息技术的发展正以前所未有的速度改变着我们的生活。无论是学习、工作还是娱乐,互联网都成为了我们不可或缺的一部分。而在线上报名这一领域,小程序的出现更是为广大用户带来了前所未有的便捷与高效。今天&#…...

【测试岗】手撕代码 - 零钱兑换
322. 零钱兑换 题目描述 给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。 你可以认为每种…...

菱形继承的类对父类的初始化、组合、多态、多态的原理等的介绍
文章目录 前言一、菱形继承的类对父类的初始化二、组合三、 多态1. 构成多态2. 虚函数3. 虚函数的重写4. 虚函数重写的两个例外1. 协变2. 析构函数的重写 5. C11 final 和 override1. final2. override 6. 设计不想被继承的类7. 重载、覆盖(重写)、 隐藏…...

React Native 在 build 的时候如果出现 `babel.config.js` 配置文件的错误
React Native 在 build 的时候如果出现以下错误, 就是 babel.config.js 配置文件的错误. Showing Recent Issues node:internal/process/promises:289triggerUncaughtException(err, true /* fromPromise */);^Error: .plugins[0][1] must be an object, false, or undefineda…...

【Linux】包管理器、vim详解及简单配置
🚀个人主页:小羊 🚀所属专栏:Linux 很荣幸您能阅读我的文章,诚请评论指点,欢迎欢迎 ~ 目录 前言一、包管理器1.1 apt1.2 yum 二、Linux编辑器——vim2.1 vim的三种模式2.2 vim普通模式常用命令2.2.1 移动…...

AVL树实现
1.AVL的概念 1.AVL树属于二叉搜索树的一种,但它不同与普通的二叉搜索树还具有以下的性质: 每一个根的左右子树的高度差的绝对值不超过1。AVL树是通过高度差去控制平衡的,所以又称作为平衡二叉搜索树。 2.AVL树实现我们引入了一个平衡因子的概…...

初始MYSQL数据库(6)—— 事务
找往期文章包括但不限于本期文章中不懂的知识点: 个人主页:我要学编程(ಥ_ಥ)-CSDN博客 所属专栏: MYSQL 目录 事务的概念 事务的ACID特性 使用事务 查看支持事务的存储引擎 事务的语法 保存点 自动/手动提交事务 事务的隔离性和…...

0基础学习PyTorch——GPU上训练和推理
大纲 创建设备训练推理总结 在《Windows Subsystem for Linux——支持cuda能力》一文中,我们让开发环境支持cuda能力。现在我们要基于《0基础学习PyTorch——时尚分类(Fashion MNIST)训练和推理》,将代码修改成支持cuda的训练和推…...

这款免费工具让你的电脑焕然一新,专业人士都在用
HiBit Uninstaller 采用单一可执行文件的形式,无需复杂的安装过程,用户可以即刻开始使用。这种便捷性使其成为临时使用或紧急情况下的理想选择。尽管体积小巧,但其功能却异常强大,几乎不会对系统性能造成任何负面影响。 这款工具的一大亮点是其多样化的功能。它不仅能够常规卸…...

Java高级Day52-BasicDAO
138.BasicDao 基本说明: DAO:data access object 数据访问对象 这样的通用类,称为 BasicDao,是专门和数据库交互的,即完成对数据库(表)的crud操作 在BasicDao 基础上,实现一张表对应一个Dao,…...

【OceanBase 诊断调优】—— SQL 诊断宝典
视频 OceanBase 数据库 SQL 诊断和优化:https://www.oceanbase.com/video/5900015OB Cloud 云数据库 SQL 诊断与调优的应用实践:https://www.oceanbase.com/video/9000971SQL 优化:https://www.oceanbase.com/video/9000889阅读和管理SQL执行…...

微服务Redis解析部署使用全流程
目录 1、什么是Redis 2、Redis的作用 3、Redis常用的五种基本类型(重要知识点) 4、安装redis 4.1、查询镜像文件【省略】 4.2、拉取镜像文件 4.3、启动redis并设置密码 4.3.1、修改redis密码【可以不修改】 4.3.2、删除密码【坚决不推荐】 5、S…...

C++之STL—常用排序算法
sort (iterator beg, iterator end, _Pred) // 按值查找元素,找到返回指定位置迭代器,找不到返回结束迭代器位置 // beg 开始迭代器 // end 结束迭代器 // _Pred 谓词 random_shuffle(iterator beg, iterator end); // 指定范围内的元素随机调…...

【驱动】地平线X3派:备份与恢复SD卡镜像
1、备份镜像 1.1 安装gparted GParted是硬盘分区软件GNU Parted的GTK+图形界面前端,是GNOME桌面环境的默认分区软件。 GParted可以用于创建、删除、移动分区,调整分区大小,检查、复制分区等操作。可以用于调整分区以安装新操作系统、备份特定分区到另一块硬盘等。 在Ubun…...