定西地网站建设,成都建设项目环境影响登记网站,搭建网站 网页,刷赞网站空间W...Y的主页 #x1f60a;
代码仓库分享 #x1f495; 前言#xff1a; 今天我们来回顾一下顺序表与链表#xff0c;针对这一块我们也有许多OJ题目供大家参考。当我们学习完顺序表链表后避免不了一些习题的练习#xff0c;这样才能巩固我们学习的内容。 话不多说#xf…
W...Y的主页
代码仓库分享 前言 今天我们来回顾一下顺序表与链表针对这一块我们也有许多OJ题目供大家参考。当我们学习完顺序表链表后避免不了一些习题的练习这样才能巩固我们学习的内容。 话不多说我们开始进入OJ习题训练 【leetcode 27.移除元素】 OJ链接 给你一个数组 和一个值 你需要原地移除所有数值等于 的元素并返回移除后数组的新长度。numsvalval 不要使用额外的数组空间你必须仅使用 额外空间并原地修改输入数组。O(1) 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。 说明: 为什么返回数值是整数但输出的答案是数组呢? 请注意输入数组是以「引用」方式传递的这意味着在函数里修改输入数组对于调用者是可见的。 题目函数接口 nums给定数组内容。numsSize数组长度大小。val移除元素。 题目要求原地删除数据不能创建任何数组这就会使原本简单的题变复杂。那我们应该怎么办呢 首先我们最先想到的方法是遍历数组遇到需要删除的内容就将数组后面的元素向前挪动一位让其覆盖。但是这种方法非常”危险“有可能导致数组越界也有可能删除遗漏。所以这不是个好方法。 接下来将一个比较新颖且简单的方法 双指针 创建两个指针变量src与dst两个指针全部指向数组开头。如果src指向的内容不是val将src的内容赋值给dst然后src与dst全部向后挪动一位。反之如果src指向的内容为valdst保持原来的位置不动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 slow1;} leetcode 88.合并两个有序数组】 OJ链接 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2另有两个整数 m 和 n 分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中使合并后的数组同样按 非递减顺序 排列。 注意最终合并后数组不应由函数返回而是存储在数组 nums1 中。为了应对这种情况nums1 的初始长度为 m n其中前 m 个元素表示应合并的元素后 n 个元素为 0 应忽略。nums2 的长度为 n 。 题目接口函数 nums1与nums2两个非递减数组。nums1Sizenums1数组大小。nums2Sizenums2数组大小。mnums1数组有效元素个数。nnums2数组有效元素个数。 其实我们可以直接将两个数组进行归并然后进行qsort排序直接完成。但是效率太低了qsort函数底层原理为快速排序法时间复杂度太高。 那有没有什么时间复杂度低的解法呢 这道题本来可以两个数组进行比较再开辟一个数组两个数组元素进行比较谁比较小就尾插到新数组中去。 但是这个题比较特殊nums1开辟的空间比较大可以放下两个数组的所有内容所以我们必须将排序好的数组放入nums1中为了保证时间复杂度为O(mn)。 但是我们可以使用这种方法的变形(三指针)。 解法我们可以倒着比较取大的依次从后往前插入。 创建三个指针一个指向nums2数组末尾处一个指向nums1有效元素末尾还有一个指向nums1数组末尾处。 然后我们进行比较即可 注意当end1与end2全部结束才可以结束循环否则会有问题。 举例num1【567000】num2【256】 代码展示 void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){int end1 m-1, end2 n-1, end mn-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然后n1n2、n2n3、n3n3-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与curprev永远指向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(fastfast-next){fast fast-next-next;slow slow-next;}return slow;
} 以上是本次全部内容有错误或不同见解的希望与博主进行沟通交流博主会继续努力将更好的博客内容带给大家你们的三连是对博主最大的支持 ❤️❤️
