W...Y的主页 😊
代码仓库分享 💕
前言:
今天我们来回顾一下顺序表与链表,针对这一块我们也有许多OJ题目供大家参考。当我们学习完顺序表链表后避免不了一些习题的练习,这样才能巩固我们学习的内容。
话不多说,我们开始进入OJ习题训练!!!
【leetcode 27.移除元素】
OJ链接
给你一个数组 和一个值 ,你需要原地移除所有数值等于 的元素,并返回移除后数组的新长度。
nums
val
val
不要使用额外的数组空间,你必须仅使用 额外空间并原地修改输入数组。
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++]; } else ret++; } 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--]; else nums1[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时循环停止结束。
代码演示: 文章来源:https://www.toymoban.com/news/detail-685214.html
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; } else return 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; }
以上是本次全部内容,有错误或不同见解的希望与博主进行沟通交流,博主会继续努力将更好的博客内容带给大家,你们的三连是对博主最大的支持!!! ❤️❤️文章来源地址https://www.toymoban.com/news/detail-685214.html
到了这里,关于顺序表链表OJ题(1)——【LeetCode】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!