顺序表链表OJ题(1)——【LeetCode】

W...Y的主页 😊

代码仓库分享 💕


 前言:

今天我们来回顾一下顺序表与链表,针对这一块我们也有许多OJ题目供大家参考。当我们学习完顺序表链表后避免不了一些习题的练习,这样才能巩固我们学习的内容。

话不多说,我们开始进入OJ习题训练!!!

【leetcode 27.移除元素】 

OJ链接

给你一个数组 和一个值 ,你需要原地移除所有数值等于 的元素,并返回移除后数组的新长度。numsvalval

不要使用额外的数组空间,你必须仅使用 额外空间并原地修改输入数组O(1)

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数,但输出的答案是数组呢?

请注意,输入数组是以「引用」方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。

题目函数接口 nums:给定数组内容。numsSize:数组长度大小。val:移除元素。


题目要求原地删除数据,不能创建任何数组,这就会使原本简单的题变复杂。那我们应该怎么办呢?

首先我们最先想到的方法是遍历数组,遇到需要删除的内容就将数组后面的元素向前挪动一位,让其覆盖。但是这种方法非常”危险“,有可能导致数组越界,也有可能删除遗漏。所以这不是个好方法。

接下来将一个比较新颖且简单的方法:

双指针: 创建两个指针变量src与dst,两个指针全部指向数组开头。如果src指向的内容不是val,将src的内容赋值给dst,然后src与dst全部向后挪动一位。反之如果src指向的内容为val,dst保持原来的位置不动,src向后挪动一位。直至src指向数组的末尾结束。

 这个方法即保证没有创建任何数组空间复杂度为O(1),也优化了暴力遍历法中时间复杂度,从O(n^2)->O(n)。

代码展示:

nt removeElement(int* nums, int numsSize, int val){int ret = 0;int valp = 0;int n = numsSize;while(ret < numsSize){if(nums[ret] != val){nums[valp++] = nums[ret++];}elseret++;}return valp;
}

【leetcode 26.删除有序数组中的重复项】

OJ链接 

给你一个 升序排列 的数组 nums ,请你原地删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ,你需要做以下事情确保你的题解可以被通过:

  • 更改数组 nums ,使 nums 的前 k 个元素包含唯一元素,并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
  • 返回 k 。

判题标准:

系统会用下面的代码来测试你的题解:

int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案int k = removeDuplicates(nums); // 调用assert k == expectedNums.length;
for (int i = 0; i < k; i++) {assert nums[i] == expectedNums[i];
}

如果所有断言都通过,那么您的题解将被通过

题目函数接口: nums:升序数组。numsSize:数组中元素个数。


思路:快慢双指针

分析:创建两个指针变量fast与slow

如果两个指针指向内容全部相同,fast向后挪动一位slow不变。

如果两个指针指向不同内容,先让slow向后移动一位,再将fast指向的内容赋值给slow,再将fast向后移动一位即可。

等到fast指向数组末尾时,循环结束!

代码演示: 

int removeDuplicates(int* nums, int numsSize){int fast = 1;int slow = 0;int n = numsSize;while(fast < n){if(nums[fast] != nums[slow]){slow++;nums[slow] = nums[fast];}else{fast++;}}return slow+1;}

leetcode 88.合并两个有序数组】 

OJ链接

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。

注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应对这种情况,nums1 的初始长度为 m + n,其中前 m 个元素表示应合并的元素,后 n 个元素为 0 ,应忽略。nums2 的长度为 n 。

题目接口函数: 

nums1与nums2:两个非递减数组。nums1Size:nums1数组大小。nums2Size:nums2数组大小。m:nums1数组有效元素个数。n:nums2数组有效元素个数。


其实我们可以直接将两个数组进行归并,然后进行qsort排序直接完成。但是效率太低了,qsort函数底层原理为快速排序法,时间复杂度太高。

那有没有什么时间复杂度低的解法呢?

这道题本来可以两个数组进行比较,再开辟一个数组,两个数组元素进行比较,谁比较小就尾插到新数组中去。

但是这个题比较特殊,nums1开辟的空间比较大,可以放下两个数组的所有内容,所以我们必须将排序好的数组放入nums1中为了保证时间复杂度为O(m+n)。

但是我们可以使用这种方法的变形(三指针)。

解法:我们可以倒着比较,取大的依次从后往前插入。 创建三个指针,一个指向nums2数组末尾处,一个指向nums1有效元素末尾,还有一个指向nums1数组末尾处。

然后我们进行比较即可: 注意当end1与end2全部结束才可以结束循环,否则会有问题。

举例:num1:【5,6,7,0,0,0】,num2:【2,5,6】

 代码展示:

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){int end1 = m-1, end2 = n-1, end = m+n-1;while(end1 >= 0 && end2 >= 0){if(nums1[end1] > nums2[end2])nums1[end--] = nums1[end1--];elsenums1[end--] = nums2[end2--];}while(end2 >= 0)nums1[end--] = nums2[end2--];}

【leetcode 206.反转链表】

OJ链接

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

 题目接口函数:

head:链表头节点


我们在反转数组时,只需要两个指针一个指向头,一个指向尾进行交换即可,最后指向中间即可结束。但是单链表没有数组的特性,不能进行逆向读取,所以这个方法行不通。

现在提供两种方法:

方法一:创建3个指针n1、n2、n3分别指向NULL、head、head->next。标记好三个位置即可进行链表反转。 让n2->next指向n1,然后n1=n2、n2=n3、n3=n3->next即可

一直循环直到n3指向NULL时循环停止结束。

代码演示: 

struct ListNode* reverseList(struct ListNode* head){struct ListNode* a = NULL;struct ListNode* b = head;struct ListNode* c = NULL;if(b)c = b->next;if(head){while(c){a = b;b = c;c = b->next;b->next = a;}head->next = NULL;return b;}elsereturn head;

 我们考虑问题就必须全面,如果链表中只有一个数则返回头指针head即可。

(头插法)方法二:

创建一个新链表头newhead,将旧链表元素挨个反向插入newhead中即可。

 

上述就是操作流程图!!!

代码演示:

struct ListNode* reverseList(struct ListNode* head){ 
struct ListNode* cur = head;struct ListNode*  newhead = NULL;while(cur){struct ListNode* next = cur->next;cur->next = newhead;newhead = cur;cur = next;}return newhead;}

【leetcode 203.移除链表元素】

OJ链接

给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。 

 题目接口函数:

head:链表头节点。val:删除目标数


思路分析:移除目标元素,我们就要遍历链表进行查找。创建两个指针prev与cur,prev永远指向cur前一个节点,用来记录。

当cur遇到目标数时,我们就可以使用prev->next =cur->next,将目标数删除。直至cur指向NULL结束。

整体思路如下:

 虽然看上去很简单,但是这种题的“极端”情况非常多。我们必须把这些特殊情况考虑清楚再去写程序才能保证万无一失。

如果遇到上述情况,使用prev->next =cur->next就不实用了,程序就会出错。那我们应该怎么办呢?

我们应该在使用prev->next =cur->next时就先把元素为val的干掉,让head指向不是val的元素。 下面是代码演示:

struct ListNode* removeElements(struct ListNode* head, int val){struct ListNode* prev = NULL, *cur = head;while(cur){if(cur->val == val){if(cur == head){head = cur->next;free(cur);cur = head;}else{prev->next = cur->next;free(cur);cur = prev->next;}}else{prev = cur;cur = cur->next;}}return head;
}

还有一种思路更清晰的方法:

创建一个新的头节点newhead,让cur遍历链表,把元素内容不是val的挪下来与newhead链接即可。

这样的思路更清晰,空间复杂度对于之前方法一没有改变,但是时间复杂度增加了。因为在newhead尾插时要找尾节点。我们可以增加一个尾指针指向newhead链表的尾节点,这样就可以优化时间复杂度。

代码演示:

struct ListNode* removeElements(struct ListNode* head, int val){struct ListNode* cur = head;struct ListNode* newhead = NULL, *tail = NULL;while(cur){if(cur->val == val){struct ListNode*der = cur;cur = cur->next;free(der);}else{if(tail == NULL){newhead = tail = cur;}else{tail->next = cur;tail = tail->next;}cur = cur->next;}if(tail){tail->next = NULL;}}return newhead;
}

 代码中有很多极端问题需要大家去想清楚,在这里就不过多讲述了,不懂可以私信我!!!

【leetcode 876.链表的中间节点】

OJ链接 

给你单链表的头结点 head ,请你找出并返回链表的中间结点。

如果有两个中间结点,则返回第二个中间结点。

题目函数接口:

head:目标链表的头节点。


分析题目:这道题我们可以使用最原始的方法进行,先将链表遍历一遍求出链表长度,然后再次进行循环找出中间值即可。

但是有些公司面试会有题目限制要求,只让我们遍历一遍找出中间值。那我们应该怎么做呢?

(快慢指针):

我们创建两个指针变量slow与fast指向链表的头节点,slow一次只移动一个节点,而fast指针一次移动两个节点。当fast指向NULL时,我们的slow节点顺理成章的就找到了中间节点。

这种类型的题目我们就可以利用速度差来达到题目要求!

代码演示: 

struct ListNode* middleNode(struct ListNode* head){struct ListNode* fast = head;struct ListNode* slow = head;while(fast&&fast->next){fast = fast->next->next;slow = slow->next;}return slow;
}

以上是本次全部内容,有错误或不同见解的希望与博主进行沟通交流,博主会继续努力将更好的博客内容带给大家,你们的三连是对博主最大的支持!!! ❤️❤️

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

PCI/PCIE总线的宏观理解

1、pcie总线协议实现的效果 (1)像访问内存一样去访问外设&#xff1b; (2)当建立好CPU地址空间到PCI/PCIE地址空间的映射关系后&#xff0c;程序访问CPU地址空间就可以达到访问PCI/PCIE地址空间的效果&#xff1b; 2、芯片地址空间 (1)32位的CPU寻址范围是4G&#xff0c;64位的…

MySQL执行更新的流程

一、加载缓存数据 引擎要执行更新语句的时候 &#xff0c;比如对“id10”这一行数据&#xff0c;他其实会先将“id10”这一行数据看看是否在缓冲池里&#xff0c;如果不在的话&#xff0c;那么会直接从磁盘里加载到缓冲池里来&#xff0c;而且接着还会对这行记录加独占锁。 二…

Spring中Bean及@Bean的理解与new对象的区别

一直在纠结一个问题&#xff1a;new创建对象和用Bean创建对象有什么区别吗&#xff1f;为什么在spring中要使用Bean&#xff1f;Bean有什么作用&#xff1f; 一、Bean是啥 1、Java面向对象&#xff0c;对象有方法和属性&#xff0c;那么就需要对象实例来调用方法和属性&#x…

Spring Bean到底是什么?有什么用?

Spring Bean是什么?有什么用&#xff1f; 一、Bean到底是什么&#xff1f;二.怎么使用bean&#xff1f;三.Bean配置四.Bean的作用域 Bean在Spring和SpringMVC中随处可见,将这个概念内化很重要&#xff0c;下面分享一下我的想法&#xff1a; 一、Bean到底是什么&#xff1f; …

spring bean是什么

原文链接&#xff1a;https://www.awaimai.com/2596.html 歪麦博客 Spring有跟多概念&#xff0c;其中最基本的一个就是bean&#xff0c;那到底spring bean是什么? Bean是Spring框架中最核心的两个概念之一&#xff08;另一个是面向切面编程AOP&#xff09;。 是否正确理解…

Spring Bean的作用域

在Spring中&#xff0c;bean作用域用于确定哪种类型的bean实例应该从Spring容器中返回给调用者。 目前Spring Bean的作用域或者说范围主要有五种。 作用域描述singleton在spring IoC容器仅存在一个Bean实例&#xff0c;Bean以单例方式存在&#xff0c;bean作用域范围的默认值…

Spring bean是什么?

Spring有跟多概念&#xff0c;其中最基本的一个就是bean&#xff0c;那到底spring bean是什么? Bean是Spring框架中最核心的两个概念之一&#xff08;另一个是面向切面编程AOP&#xff09;。 是否正确理解 Bean 对于掌握和高效使用 Spring 框架至关重要。 遗憾的是&#xff0…

什么是bean

什么是bean&#xff1f; bean是计算机自动生成的类&#xff0c;bean是一个由Spring IoC容器实例化、组装和管理的对象。也就是说&#xff0c;bean并不是程序员编辑的&#xff0c;而是程序运行时&#xff0c;由spring通过反射生成的。在程序中&#xff0c;我们并不使用代码去ne…

Bean介绍

1.Bean 简介 在 Spring 中&#xff0c;所有被IOC 容器管理的&#xff0c;构成应用核心骨架的对象都被成为 Bean&#xff0c;它是由容器来实例化、装配、管理的对象。此外&#xff0c;它也是你应用中众多对象的一个。Bean 以及依赖的实例化和装配等工作全部是由容器中的配置元信…

Bean专题——什么是Bean?怎么注册、使用?生命周期?作用域?

1.什么是Bean&#xff1f; Bean是被实例的、组装的、及被Spring容器管理的Java对象。Spring容器会自动完成Bean对象的实例化。创建应用对象之间的协作关系的行为被称为&#xff1a;装配&#xff0c;这就是依赖注入的本质。 2.Spring三种装配方案 1.隐式的bean发现机制和自动…

【Spring第三篇】什么是Bean?

在Spring 中&#xff0c;构成应用程序主干并由Spring IoC容器管理的对象称为bean。bean是一个由Spring IoC容器实例化、组装和管理的对象。 我们总结如下&#xff1a; 1.bean是对象&#xff0c;一个或者多个不限定 2.bean由Spring中一个叫IoC的东西管理 3.我们的应用程序由一个…

大数据-玩转数据-Flink窗口函数

一、Flink窗口函数 前面指定了窗口的分配器, 接着我们需要来指定如何计算, 这事由window function来负责. 一旦窗口关闭, window function 去计算处理窗口中的每个元素. window function 可以是ReduceFunction,AggregateFunction,or ProcessWindowFunction中的任意一种. Reduc…

软考:中级软件设计师:网络类型与拓扑结构,网络规划与设计,ip地址与子网划分,特殊含义的IP地址

软考&#xff1a;中级软件设计师:网络类型与拓扑结构 提示&#xff1a;系列被面试官问的问题&#xff0c;我自己当时不会&#xff0c;所以下来自己复盘一下&#xff0c;认真学习和总结&#xff0c;以应对未来更多的可能性 关于互联网大厂的笔试面试&#xff0c;都是需要细心准…

Qt入门教程【Core篇】Layout布局(布局管理器、手动布局)

&#x1f608;「编程小鱼酱秘密基地」&#xff1a;传送门 &#x1f608;「CSDN主页」&#xff1a;传送门 &#x1f608;「Bilibil首页」&#xff1a;传送门 &#x1f608;「网易云课堂」&#xff1a;传送门 &#x1f608;「CSDN学院」&#xff1a;传送门 &#x1f608;「51CTO学…

前端布局 Flex(弹性)布局

1. flex布局优点 操作方便&#xff0c;布局极为简单&#xff0c;移动端应用很广泛 pc端浏览器支持情况较差 IE11或者更低版本&#xff0c;不支持或仅部分支持 2. flex布局原理 flex意为“弹性布局”&#xff0c;用来为盒状模型提供最大的灵活性&#xff0c;任何一个容器都…

Java BorderLayout(边框布局)布局管理器

BorderLayout BorderLayout 将容器分为 EAST 、 SOUTH 、 WEST 、 NORTH 、 CENTER五个区域&#xff0c;普通组件可以被放置在这 5 个区域的任意一个中 。 BorderLayout布局 管理器的布局示意图如图所示 。 当改变使用 BorderLayout 的容器大小时&#xff0c; NORTH 、 SOUTH …

java:布局方法(网格布局)

网格布局 一、简单说明二、关键代码三、流程图四、例子说明1. 有17个“按钮”排列&#xff08;1&#xff09;源码A&#xff08;2&#xff09;运行效果 2. 有36个“按钮”排列&#xff08;1&#xff09;源码B&#xff08;2&#xff09;源码B运行效果 3. 有12个“按钮”排列&…

Grid布局介绍

1、什么是Grid布局 ​     Grid布局即网格布局&#xff0c;是一种新的css模型&#xff0c;一般是将一个页面划分成几个主要的区域&#xff0c;定义这些区域的大小、位置和层次等关系&#xff0c;是目前唯一一种css二维布局。 2、和flex布局的区别 ​     Grid布局和fle…

Java GridLayout(网格布局)布局管理器

GridLayout&#xff08;网格布局&#xff09; ​ GridLayout 布局管理器将容器分割成纵横线分隔的网格 &#xff0c; 每个网格所占的区域大小相同。当向使用 GridLayout 布局管理器的容器中添加组件时&#xff0c; 默认从左向右、 从上向下依次添加到每个网格中 。 与 FlowLay…

css经典布局——圣杯布局

圣杯布局和双飞翼布局一直是前端面试的高频考点&#xff0c;圣杯布局的出现是来自由 Matthew Levine 在 2006 年写的一篇文章 《In Search of the Holy Grail》。 比起双飞翼布局&#xff0c;它的起源不是源于对页面的形象表达。在西方&#xff0c;圣杯是表达“渴求之物”的意思…