网站seo诊断湖南岚鸿诊断,北京做网站建设多少钱,会员管理网站建设,免费素材库网目录 前言 题目一#xff1a;删除有序数组中的重复项 思路#xff1a; 题解#xff1a; 题目二#xff1a;合并两个有序数组 思路#xff1a; 分析#xff1a; 题解#xff1a; 题目三#xff1a;反转链表 思路#xff1a; 分析#xff1a; 题解#xff1a; 题目四删除有序数组中的重复项 思路 题解 题目二合并两个有序数组 思路 分析 题解 题目三反转链表 思路 分析 题解 题目四移除链表元素 思路一 分析 题解 思路二 分析 题解 总结 前言 无论是面试准备还是日常编码实践解决与顺序表和链表相关的算法问题都是不可避免的挑战本篇文章旨在帮助你巩固和提升这两个重要数据结构的理解和应用能力。 题目一删除有序数组中的重复项 题目描述 示例与提示 思路 题目中的数组是一个升序的数组依据这个点我们可以知道相同的元素都是紧挨着的那要想保持升序后一个元素一定比不等于当前元素且比当前元素大。和前边删除元素的思路类似。
题解
int removeDuplicates(int* nums, int numsSize){
int pos0;int src0;while(srcnumsSize-1){if(nums[src]!nums[src1]){nums[pos]nums[src];}elsesrc;}nums[pos]nums[src];//为了防止数组越界访问导致最后一个元素没有进行赋值最后在这里补上return pos;
} 题目二合并两个有序数组 题目描述 示例与提示 合并两个有序数组的思想叫做归并这种思路在后续的学习中也会经常遇到。有的同学可能会有这样的思路将两个元素合并然后qsort排序一下这样暴力求解。这样解题也可以但我们学习了空间复杂度和时间复杂度就要考虑到复杂度问题以写出好的程序。 思路 注意题目中给的是非递减排列的整数数组举个例子13457。这样的数组属于递增数组1233356。这样的数组属于非递减数组。 了解清楚题意后我们介绍一下解题思路我们可以依次比较两数组中的元素然后把小的尾插到新数组这个就是归并的思想。但是这道题目有点不一样它的第一个数组会很大是两个数组有效数据个数的和这里就要求我们把数据归并到第一个数组。
那这道题应该怎么解决呢 前边介绍的归并思想我们是正着比较然后尾插那这道题我们是不是可以倒着比较然后尾插到第一个数组。 分析 理解了解题的思路后我们在进行更深一步的分析由于力扣的题目大都是接口型题目在调试时会很麻烦这就是我们刷不动题的原因之一做好全面的分析才能更高效的解决问题。 情况一 从末尾开始依次比较较大的数字插入到数组一的末尾 依次比较并进行插入。 情况二 两个数组依然是末尾数据进行比较然后尾插到数组一但是这次不同的是数组一遍历完后还并没有结束此时的数据如下 这里就需要再将数组二剩下的数据继续插入到数组一当中。 题解
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
int end1m-1;
int end2n-1;
int endmn-1;while(end10 end20){if(nums1[end1] nums2[end2]){nums1[end--]nums1[end1--];}else{nums1[end--]nums2[end2--];}}while(end2 0){nums1[end--] nums2[end2--];}
} 使用3个变量依次存储第一个数组的有效数据的末尾第二个数组的末尾以及第一个数组的末尾。谁大就把他插入到nums1的末尾最后如果第二个数组没有遍历完就将剩余数据依次插入到nums1中。
题目三反转链表 题目描述 思路 数组的反转很简单最后一个元素和第一个元素交换然后一个往前一个往后循环遍历但这个是单链表没法向前遍历。那要怎么解决呢我们可以这样做遍历这个链表将每个节点依次改为指向前一个节点但要确保后续节点不丢失。这里我们就可以创建3个结构体指针一个指向NULL一个指向第一个节点最后指向第二个节点以便于记录链表后续节点。
分析 假设初始是这样的一个链表 创建3跟结构体指针改变节点指向后向后遍历 有人疑惑链表不是不可以向前遍历吗那n1怎么到n2的位置我们可以直接把n2赋值给n1然后把n3赋值给n2n3通过指针继续向后遍历。 当n2为NULL时就结束。 题解 分析之后我们就进行具体实现
struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* n1,*n2,*n3;n1NULL;n2head;if(n2!NULL)n3n2-next;while(n2){n2-nextn1;n1n2;n2n3;if(n3!NULL)n3n3-next;}return n1;
} 需要注意的是空指针问题当n3为空时就不要继续向后遍历了。 题目四移除链表元素 题目描述 思路一 这里的思路中规中矩遍历这个链表与遇到要删除的val值就删除但这里需要注意一点特殊情况尽可能的去多虑特殊情况。 分析 假设初始时给这样一个链表要删除的是6. 但是单一的使用指针找到了val的节点又没法删需要知道前一个节点。那可不可以使用替换法把4替换到6节点的位置遇到val值节点就把后一个节点替换过来这样就不用使用两个指针了但如果要删除的节点是尾节点呢它可没有后一个节点。所以我们还是使用传统的方法。创建一个指针记录前一个节点。 把val值前一个节点next改为val后一个节点的地址释放掉cur指向的节点。如果删除节点是最后一个将prev指向节点的next置为NULL。 那这种情况呢如果要删除的节点是头prev就行不通了。所有我们还需要再多考虑一下头节的情况进行特殊处理。 初始情况下cur和head都指向头节点把cur的下一个节点赋值为head然后释放掉cur指向的第一个节点再把新的头head赋给cur。这样就可以解决了。
题解 分析完整体思路后我们进行代码实现代码如下
struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* prevNULL;struct ListNode* curhead;while(cur){if(cur-valval){if(curhead){headcur-next;free(cur);curhead;}else{prev-next cur-next;free(cur);curprev-next;}}else{prevcur;curcur-next;}}return head;
} 思路二 除了传统的方法还有另外一种方法——尾插法。遍历原链表如果不是val就尾插到新链表。
分析 可以先创建一个新的链表头初始时链表头为空然后依次尾插插入节点。 这种方法更加简单快捷没有那么多需要考虑的特殊情况最后返回新的头。
题解 这种方法思路虽然很简单但在实现时有很多需要注意的点
struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* curhead;struct ListNode* newheadNULL,*tailNULL;while(cur){if(cur-valval){struct ListNode* delcur;curcur-next;free(del);}else {if(tailNULL)//考虑初始时头和尾都为NULL的情况{tailnewheadcur;}else{tail-nextcur;tailtail-next;}curcur-next;}}if(tail)tail-nextNULL;//遍历完之后需要将尾节点next置为NULL此外还需要注意tail是否为NULL。return newhead;
} 在刷题时我们会发现很多的操作都是基于我们前边学习的单链表中基本操作的变形此外解题的思路在很多情况下都是通用的只需略微变形就可解决问题。所有一定要学会举一反三。 总结 刷题不仅是为了应对面试和编码实践更是为了培养自己的问题解决能力和学习能力。无论是顺序表还是链表它们都是构建更复杂数据结构的基石掌握它们对你的编程之路至关重要。最后感谢阅读
