【HOT100第五天】搜索二维矩阵 II,相交链表,反转链表,回文链表

240.搜索二维矩阵 II

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性:

  • 每行的元素从左到右升序排列。
  • 每列的元素从上到下升序排列。

先动手写写最简单方法,二重循环。

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int m=matrix.size(),n=matrix[0].size();if(m==0||n==0) return{};for(auto& itx:matrix){for(auto& itxy:itx){if(itxy==target) return true;}}return false;}
};

优化方法的话,根据昨天做的题,感觉大多数矩阵相关的题目都是依靠找规律,那我们再看看例图:

 以“5”这一项为例,左边和上边的数比 5 小,右边和下边的数比 5 大。可以利用这一特点,从左下角或者右上角开始顺藤摸瓜。

以从右上角为例,如果target小于15,就向左移一位,如果target大于15,就向右移一位,以此类推,如果已经移出了矩阵的边界,说明没找到target的值,就返回false。

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int m=matrix.size(),n=matrix[0].size();if(m==0||n==0) return{};int x=0,y=n-1;while(x<=m-1&&y>=0){if(matrix[x][y]==target) return true;else if(matrix[x][y]>target){y--;}else{x++;}}return false;}
};

160. 相交链表

给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。

图示两个链表在节点 c1 开始相交

题目数据 保证 整个链式结构中不存在环。

注意,函数返回结果后,链表必须 保持其原始结构 。

自定义评测:

评测系统 的输入如下(你设计的程序 不适用 此输入):

  • intersectVal - 相交的起始节点的值。如果不存在相交节点,这一值为 0
  • listA - 第一个链表
  • listB - 第二个链表
  • skipA - 在 listA 中(从头节点开始)跳到交叉节点的节点数
  • skipB - 在 listB 中(从头节点开始)跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构,并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点,那么你的解决方案将被 视作正确答案 。

 虽然是简单题但其实是最让我痛苦的一道。!看一眼题目感觉还好理解,一看给的例子就懵了。

好了这种情况下先不要急,看一下方法体吧。输入是两个链表的头结点,输出的是相交节点。那目的先可以初步确定了。

一开始看到可能会没什么思路,这是正常的,因为题目对相交链表的表述不太清楚。这道题中相交链表的定义是一个从某一结点开始,两链表相交后,后面的结点完全相同。

验证一下它说的是不是这样,我添加了一个用例,在中间的某一位置相交,又在后面分开:

可见确实如此,糟老头子坏得很啊。

这样的话,两个链表相交的过程就可以简化成下面这样了👇

a1->a2->...->ai->c1->c2->...->cn
b1->b2->...->bj

设想一下,如果 1~i 和 1~j 的值相同就好了,那就意味着这两个链表长度相同,A和B链表上的指针到达相交结点的时间是相同的。

但事实是两个链表不一定长度相同,不过思路还是一样,是不是只要A和B两个链表的指针同时到达相交结点,就可以找到这个结点了?

我们现在已知,遍历A链表需要指针移动(i+n)次,遍历B链表需要指针移动(j+n)次,不如让A链表的指针遍历完A后再遍历一遍B链表,并且B链表指针遍历完B后再遍历A链表,这样的话,每一个指针都一共要移动(i+j+2n)次,那么第一个找到的满足(pa==pb)的结点,就一定是相交结点。

如果两个链表没有重合也不用担心,两个指针会在链表的尾部相遇,然后返回一个空指针。

这样就可以写出代码:

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {if(headA==nullptr||headB==nullptr) return nullptr;ListNode *pa=headB,*pb=headA;while(pa!=pb){if(pa) pa=pa->next;else pa=headB;if(pb) pb=pb->next;else pb=headA;}return pa;}
};

但再具体想一想,如果两链表后面的结点不一样,只有中间连续的1~n的结点相交的情况下,这个方法能不能用呢?答案是不能!因为相交结点后面的长度会影响到指针到达相交节点。比如说链表A如果是(i1+n+i2),链表B是(j1+n+j2),那用之前的两个都遍历的方法,A的指针pa第二次到达相交结点走过的路程是(i1+n+i2+j1),而链表B第二次到达相交结点走过的路程是(j1+n+j2+i1)!!!

 206. 反转链表

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

反转无非是把 a1 -> a2 -> a3 ->..._> an -> nullptr 改成 nullptr <- a1 <- a2 <-...<- an。

比如遍历用的指针是p,我们把p的next改成前驱结点就好了。不过前驱结点需要提前记录,而且为了在改变了p->next之后还可以继续遍历,就需要先把后继p->next存下来再改成前驱即可。所以整理一下,对结点的调整步骤为:

1. 保存后继

2. 把next改成前驱结点

3. 把当前结点改成前驱

4. 让p移向下一个结点

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* reverseList(ListNode* head) {if(!head) return nullptr;ListNode* p=head;ListNode* pre=nullptr;while(p!=nullptr){ListNode* next=p->next;p->next=pre;pre=p;p=next;}return pre;}
};

234. 回文链表

给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false 。

克服恐惧的最好方法就是避免恐惧(。。),不会操作链表但是向想写出来,就先把它复制进数组里再对它使用双指针!过了就是胜利✌

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:bool isPalindrome(ListNode* head) {vector<int> nums;while(head!=nullptr){nums.emplace_back(head->val);head=head->next;}int left=0,right=nums.size()-1;while(left<right){if(nums[left]==nums[right]){left++;right--;}else{return false;}}return true;}
};

说笑了,下面看看正规方法来做。

 我们刚刚既然已经写过了反转链表,那这一次不如用上。

直接在它给的链表上改,把前一半链表都反转,后一半链表不变,然后用两个指针分别遍历前后两段,一边遍历一边比较。

如何实现只反转一半?怎么找到链表的中点?这里可以使用快慢指针,快指针一次进两格,慢指针一次进一格,那么当fast或者fast->next为空时,slow所在的位置就是中点了。

不过要注意,当结点数为奇数时,我们需要用中点后面那个点作为后半部分的起始点。 

如何判断链表是奇数个还是偶数个?在纸上画一下,以题目提供的测试用例为例:

fast经历的结点索引值是0,2,“4”。所以当结点是偶数个时,fast==nullptr,以此类推,当结点为奇数个时,fast->next=nullptr。

梳理一下目前我们用到的变量,快慢指针是肯定的,fast用来确定奇偶和中点,slow摸到中点顺便用于反转链表,pre是反转用到的前驱结点,next是反转用到的后继结点。

当摸到中点并且完成反转时,我们的链表变成了这样👇(以4个和5个结点的链表为例)

a1 <- a2   a3 -> a4 -> a5 【pre在a2的位置,slow在a3的位置,next在a4的位置,fast在a5的位置】

a1 <- a2  a3 -> a4 【pre在a2的位置,slow在a3的位置,next在a4的位置,fast在a4后面的位置】

因此,偶数个结点的话用pre和slow来遍历一下链表就行了,奇数个结点的话就把slow处理一下再遍历。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:bool isPalindrome(ListNode* head) {if(head==nullptr||head->next==nullptr) return true;ListNode* slow=head;ListNode* fast=head;ListNode* pre=nullptr;ListNode* next=nullptr;//快指针在链表尾部,慢指针在中点while(fast&&fast->next){fast=fast->next->next;next=slow->next;slow->next=pre;pre=slow;slow=next;}//fast为空是偶数,fast不为空是奇数if(fast!=nullptr){slow=slow->next;}//利用pre和slow比较是否相等while(slow!=nullptr&&pre!=nullptr){if(slow->val!=pre->val){return false;}slow=slow->next;pre=pre->next;}return true;}
};

这题下次还是用复制进数组的方法吧(。。。。)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/475637.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

从技术到产品:第三方美颜API助力实时直播平台的开发详解

众所周知&#xff0c;开发一套完整的美颜功能不仅耗时耗力&#xff0c;还需要大量的算法调优与硬件优化。为此&#xff0c;第三方美颜API成为越来越多开发者的优先选择。本篇文章&#xff0c;小编将从技术到产品&#xff0c;深入探讨第三方美颜API如何助力直播平台的快速开发。…

《深入理解 Spring MVC 工作流程》

一、Spring MVC 架构概述 Spring MVC 是一个基于 Java 的轻量级 Web 应用框架&#xff0c;它遵循了经典的 MVC&#xff08;Model-View-Controller&#xff09;设计模式&#xff0c;将请求、响应和业务逻辑分离&#xff0c;从而构建出灵活可维护的 Web 应用程序。 在 Spring MV…

大数据新视界 -- 大数据大厂之 Impala 性能优化:融合人工智能预测的资源预分配秘籍(上)(29 / 30)

&#x1f496;&#x1f496;&#x1f496;亲爱的朋友们&#xff0c;热烈欢迎你们来到 青云交的博客&#xff01;能与你们在此邂逅&#xff0c;我满心欢喜&#xff0c;深感无比荣幸。在这个瞬息万变的时代&#xff0c;我们每个人都在苦苦追寻一处能让心灵安然栖息的港湾。而 我的…

【MySQL-3】表的约束

目录 1. 整体学习的思维导图 2. 非空约束 3. default约束 4. No Null和default约束 5. 列描述 comment 6. Zerofill 7. 主键 primary key 复合主键 8. 自增长 auto_increment 9. 唯一键 10. 外键 11. 实现综合案例 1. 整体学习的思维导图 2. 非空约束 正如该标题一…

【Linux】Namespace

一、概念 Linux Namespace 是 Linux 内核提供的一种特性&#xff0c;用于对系统资源进行隔离。通过 Namespace&#xff0c;不同的进程组可以拥有独立的系统资源视图&#xff0c;即使它们在同一台物理机器上运行。这种隔离机制使得容器技术成为可能&#xff0c;因为它允许在单个…

在MATLAB中实现自适应滤波算法

自适应滤波算法是一种根据信号特性自动调整滤波参数的数字信号处理方法&#xff0c;其可以有效处理噪声干扰和信号畸变问题。在许多实时数据处理系统中&#xff0c;自适应滤波算法得到了广泛应用。在MATLAB中&#xff0c;可以使用多种方法实现自适应滤波算法。本文将介绍自适应…

Python学习------第十天

数据容器-----元组 定义格式&#xff0c;特点&#xff0c;相关操作 元组一旦定义&#xff0c;就无法修改 元组内只有一个数据&#xff0c;后面必须加逗号 """ #元组 (1,"hello",True) #定义元组 t1 (1,"hello") t2 () t3 tuple() prin…

软件测试—— Selenium 常用函数(一)

前一篇文章&#xff1a;软件测试 —— 自动化基础-CSDN博客 目录 前言 一、窗口 1.屏幕截图 2.切换窗口 3.窗口设置大小 4.关闭窗口 二、等待 1.等待意义 2.强制等待 3.隐式等待 4.显式等待 总结 前言 在前一篇文章中&#xff0c;我们介绍了自动化的一些基础知识&a…

Rust 力扣 - 746. 使用最小花费爬楼梯

文章目录 题目描述题解思路题解代码题目链接 题目描述 题解思路 我们使用a&#xff0c;b分别记录n - 2层向上爬的最小花费&#xff0c;n - 1层向上爬的最小花费 到达楼梯顶第N层&#xff0c;只能从N - 1层或者N - 2层向上爬 所以爬到第N层的最小花费 第N - 1层向上爬和第N - …

VRT: 关于视频修复的模型

VRT: 关于视频修复的模型 1. 视频修复的背景与重要性背景介绍&#xff1a;重要性&#xff1a; 2. VRT的重要性和研究背景VRT的背景&#xff1a;VRT的重要性&#xff1a; 3. 视频修复概述3.1 定义与目标3.2 与单图像修复的区别3.3 对时间信息利用的需求 4. VRT模型详解4.1 整体框…

关于C++地址交换的实现

关于地址的交换实现&#xff0c;我们要使用指针引用的方式进行&#xff0c;例如&#xff1a; #include <iostream>// 定义函数交换两个整型指针的地址 void swapIntPtrAddresses(int* &ptr1, int* &ptr2) {int *temp ptr1;ptr1 ptr2;ptr2 temp; }int main() …

HarmonyOS ArkUI(基于ArkTS) 常用组件

一 Button 按钮 Button是按钮组件&#xff0c;通常用于响应用户的点击操作,可以加子组件 Button(我是button)Button(){Text(我是button)}type 按钮类型 Button有三种可选类型&#xff0c;分别为胶囊类型&#xff08;Capsule&#xff09;、圆形按钮&#xff08;Circle&#xf…

SpringBoot学习笔记(一)

一、Spring Boot概述 &#xff08;一&#xff09;微服务概述 1、微服务 微服务&#xff08;英语&#xff1a;Microservices&#xff09;是一种软件架构风格&#xff0c;它是以专注于单一责任与功能的小型功能区块 (Small Building Blocks) 为基础&#xff0c;利用模块化的方式…

C++初阶(十三)--STL--vector的使用

目录 ​编辑 一、vector的基本介绍 二、vector的使用 1.构造函数的介绍 2.容量操作 size和capacity reserve和resize empty 3.vector的遍历 operator[ ](size_t n) 迭代器使用 begin和end rbegin和rend 4.vector的增删查改 push_back和pop_back insert和erase fi…

用Python爬虫“偷窥”1688商品详情:一场数据的奇妙冒险

引言&#xff1a;数据的宝藏 在这个信息爆炸的时代&#xff0c;数据就像是一座座等待挖掘的宝藏。而对于我们这些电商界的探险家来说&#xff0c;1688上的商品详情就是那些闪闪发光的金子。今天&#xff0c;我们将化身为数据的海盗&#xff0c;用Python这把锋利的剑&#xff0…

matlab的函数名和函数文件名的关系(编程注意事项)

在MATLAB中&#xff0c;函数名和函数文件名之间有着重要的关系。以下是它们之间的关系以及在编程时需要注意的事项 文章目录 函数名与函数文件名的关系编程时的注意事项结论 函数名与函数文件名的关系 一致性要求&#xff1a; 在MATLAB中&#xff0c;函数文件的文件名必须与函数…

【Redis】持久化机制RDB与AOF

一、RDB RDB模式是就是将内存中的数据存储到磁盘中&#xff0c;等到连接断开的时候会进行持久化操作。但是如果服务器宕机&#xff0c;会导致这个持久化机制不会执行&#xff0c;但是内存中的文件会直接丢失。所以可以设置一个触发机制&#xff0c;save 60 1000 就是代表60秒 执…

基于Lora通讯加STM32空气质量检测WIFI通讯-分享

目录 目录 前言 一、本设计主要实现哪些很“开门”功能&#xff1f; 二、电路设计原理图 1.电路图采用Altium Designer进行设计&#xff1a; 2.实物展示图片 三、程序源代码设计 四、获取资料内容 前言 随着环境污染问题的日益严重&#xff0c;空气质量的监测与管理已经…

【MySQL】ubantu 系统 MySQL的安装与免密码登录的配置

&#x1f351;个人主页&#xff1a;Jupiter. &#x1f680; 所属专栏&#xff1a;MySQL初阶探索&#xff1a;构建数据库基础 欢迎大家点赞收藏评论&#x1f60a; 目录 &#x1f4da;mysql的安装&#x1f4d5;MySQL的登录&#x1f30f;MySQL配置免密码登录 &#x1f4da;mysql的…

【STK学习】part2-星座-目标可见性与覆盖性分析

【Satellite Tool Kit】学习并深入了解卫星/星座生成、可见性分析、覆盖性分析等知识&#xff0c;并基于STK软件实现对应数据的导出&#xff0c;以用于算法的约束输入。 文章目录 一、学习目标二、学习内容2.1 星地可见性分析2.1.1 单星单地2.1.2 单星多地2.1.3 多星单地 2.2 星…