数据结构—顺序表超经典算法

Ne0inhk

— 19 min read
数据结构—顺序表超经典算法

数据结构—顺序表链表经常用到的算法

所有题目链接

移除元素
删除有序数组中的重复项
合并两个有序数组
移除链表元素
反转链表
链表的中间节点
合并两个有序链表
链表分割
链表的回文结构
相交链表
环形链表I
环形链表II

顺序表算法题（双指针法）

移除元素

题目链接↓
移除元素

在这里插入图片描述

题目讲解↓

思路：双指针法，创建两个变量dst,src如果src指向的数据是val，src++如果src指向的数据不是val，赋值(src给dst)，src和dsr都++src在前面探路（找非val值），dst在后面站岗（保存非val值）
时间复杂度：O(N)
空间复杂度：O(1)
//1.移除元素intremoveElement(int* nums,int numsSize,int val){//创建两个变量int src =0, dst =0;;while(src < numsSize){//src指向的数据是val，src++//src指向的数据不是val，赋值整体再++if(nums[src]!= val){ nums[dst]= nums[src]; dst++;} src++;}return dst;}
在这里插入图片描述

删除有序数组中的重复项

题目链接↓
删除有序数组中的重复项

在这里插入图片描述

题目讲解↓

思路：双指针法，创建两个变量，分别指向数组起始和下一个位置如果src的值和dst的值相等，src++如果src的值和dst的值不相等，dst++，src赋值给dst，src++
时间复杂度：O(N)
空间复杂度：O(1)
//2.删除有序数组中的重复项intremoveDuplicates(int* nums,int numsSize){//创建两个变量 分别指向数组起始和下一个位置int src =1, dst =0;//src的值和dst的值相等，src++ //src的值和dst的值不相等，dst++，src赋值给dst，src++ while(src < numsSize){if(nums[src]!= nums[dst]){ dst++; nums[dst]== nums[src];} src++;}return dst +1;}//优化:如果 ++dst == src，就会造成自己给自己赋值，因此优化一下intremoveDuplicates(int* nums,int numsSize){//创建两个变量 分别指向数组起始和下一个位置int src =1, dst =0;//src的值和dst的值相等，src++ //src的值和dst的值不相等，dst++，src赋值给dst，src++ while(src < numsSize){if(nums[src]!= nums[dst]&&++dst != src){ nums[dst]== nums[src];} src++;}return dst +1;}
在这里插入图片描述

合并两个有序数组

题目链接↓
合并两个有序数组

在这里插入图片描述

题目讲解↓

思路：从后往前遍历数组，找大（谁大谁先往后放）
时间复杂度O(N)
//3.合并两个有序数组voidmerge(int* nums1,int nums1Size,int m,int* nums2,int nums2Size,int n){//创建三个变量int l1 = m -1, l2 = n -1, l3 = m + n -1;while(l1 >=0&& l2 >=0){//比较谁大，谁往后放if(nums1[l1]> nums2[l2]){ nums1[l3--]= nums1[l1--];}else{ nums1[l3--]= nums2[l2--];}}//l1越界（需要特殊处理）while(l2 >=0){ nums1[l3--]= nums2[l2--];}//l2越界（不需要处理）//不会同时越界}
在这里插入图片描述

链表算法题（快慢指针，三指针法，创建新链表法）

移除链表元素

题目链接↓
移除链表元素

在这里插入图片描述

题目讲解↓

思路：创建新链表，将原链表中不为val的节点拿下来尾插
时间复杂度：O(N)
空间复杂度：O(1)
此处创建新链表菲真创建新链表，而是通过修改原本的链表 \color{red}{此处创建新链表菲真创建新链表，而是通过修改原本的链表} 此处创建新链表菲真创建新链表，而是通过修改原本的链表
//4.移除链表元素/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */typedefstructListNode ListNode;structListNode*removeElements(structListNode* head,int val){ ListNode* newHead,* newTail; newHead = newTail =NULL; ListNode* pcur = head;while(pcur){//判断pcur节点的值是否为valif(pcur->val != val){//尾插 分类（链表是否为空）if(newHead ==NULL){//链表为空 newHead = newTail = pcur;}else{//链表非空 newTail->next = pcur; newTail = pcur;}} pcur = pcur->next;}//最后别忘了把尾节点的next置为空，不然会把剩下的节点带过来if(newTail){ newTail->next =NULL;}return newHead;}

反转链表

题目链接↓
反转链表

在这里插入图片描述

题目讲解↓

思路1：创建新链表，遍历原链表将节点头插到新链表中
此处创建新链表菲真创建新链表，通过不断拆解这两个链表合为一个， \color{red}{此处创建新链表菲真创建新链表，通过不断拆解这两个链表合为一个，} 此处创建新链表菲真创建新链表，通过不断拆解这两个链表合为一个，
因此要格外注意保存下一个节点和尾节点的 n e x t 为 N U L L \color{red}{因此要格外注意保存下一个节点和尾节点的next为NULL} 因此要格外注意保存下一个节点和尾节点的next为NULL
时间复杂度O(N)
空间复杂度O(1)
思路2：创建三个指针，改变指针的指向
时间复杂度O(N)
空间复杂度O(1)
//5.反转链表typedefstructListNode ListNode;structListNode*reverseList(structListNode* head){ ListNode* pcur = head; ListNode* newHead = head;while(pcur){//头插 ListNode* next = pcur->next;//保存下一个节点 pcur->next = newHead; newHead = pcur; pcur = next;}if(head)//注意尾节点，避免成环{ head->next =NULL;}return newHead;}
typedefstructListNode ListNode;structListNode*reverseList(structListNode* head){if(head ==NULL)//需要处理一下特殊情况{returnNULL;}//创建三个指针 ListNode* n1,* n2,* n3; n1 =NULL, n2 = head, n3 = n2->next;while(n2){ n2->next = n1; n1 = n2; n2 = n3;if(n3){ n3 = n3->next;}}return n1;}
在这里插入图片描述


在这里插入图片描述

链表的中间节点

题目链接↓
链表的中间节点

在这里插入图片描述

题目讲解↓

思路：快慢指针，慢指针每次走一步，快指针每次走两步
时间复杂度：O(N)
  • 画出思路
在这里插入图片描述
//6.链表的中间节点/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */typedefstructListNode ListNode;structListNode*middleNode(structListNode* head){//创建快慢指针 ListNode* slow = head; ListNode* fast = head;while(fast !=NULL&& fast->next !=NULL)//用到短路（方向不能反，否则空指针解引用）{ slow = slow->next; fast = fast->next->next;}return slow;}
在这里插入图片描述

合并两个有序链表

题目链接↓
合并两个有序链表

在这里插入图片描述

题目讲解↓

思路：创建新链表，遍历并比较原链表中节点的值，小的尾插到新链表中
此处创建新链表菲真创建新链表，通过不断拆解这两个链表合为一个， \color{red}{此处创建新链表菲真创建新链表，通过不断拆解这两个链表合为一个，} 此处创建新链表菲真创建新链表，通过不断拆解这两个链表合为一个，
因此要格外注意保存下一个节点和尾节点的 n e x t 为 N U L L \color{red}{因此要格外注意保存下一个节点和尾节点的next为NULL} 因此要格外注意保存下一个节点和尾节点的next为NULL
时间复杂度：O(N)
//7.合并两个有序链表/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */typedefstructListNode ListNode;structListNode*mergeTwoLists(structListNode* list1,structListNode* list2){if(list1 ==NULL){return list2;}if(list2 ==NULL){return list1;}//创建空链表 ListNode* newHead,* newTail; newHead = newTail =NULL;//遍历原链表 ListNode* l1 = list1; ListNode* l2 = list2;while(l1 !=NULL&& l2 !=NULL){if(l1->val < l2->val){//l1尾插if(newHead ==NULL){//空链表 newHead = newTail = l1;}else{//非空链表 newTail->next = l1; newTail = newTail->next;} l1 = l1->next;//保存下一个节点}else{//l2尾插if(newHead ==NULL){//空链表 newHead = newTail = l2;}else{//非空链表 newTail->next = l2; newTail = newTail->next;} l2 = l2->next;}}//l1为空，l2为空if(l1){ newTail->next = l1;}if(l2){ newTail->next = l2;}return newHead;}
在这里插入图片描述
  • 以上的代码有些冗余（if判断NULL太多)，如果创捷一个哨兵位可以更加简洁
typedefstructListNode ListNode;structListNode*mergeTwoLists(structListNode* list1,structListNode* list2){if(list1 ==NULL){return list2;}if(list2 ==NULL){return list1;}//创建空链表 ListNode* newHead,* newTail; newHead = newTail =(ListNode*)malloc(sizeof(ListNode));//申请哨兵位//遍历原链表 ListNode* l1 = list1; ListNode* l2 = list2;while(l1 !=NULL&& l2 !=NULL){if(l1->val < l2->val){//l1尾插 newTail->next = l1; newTail = newTail->next; l1 = l1->next;//保存下一个节点}else{//l2尾插 newTail->next = l2; newTail = newTail->next; l2 = l2->next;}}//l1为空，l2为空if(l1){ newTail->next = l1;}if(l2){ newTail->next = l2;} ListNode* retHead = newHead->next;free(newHead); newHead =NULL;return retHead;}
在这里插入图片描述

链表分割

题目链接↓
链表分割

在这里插入图片描述

题目讲解↓

思路:创建两个链表(小链表、大链表)，遍历原链表，小的尾插到小链表中，大的尾插到大链表中，大链表和小链表首尾相连
此处创建新链表菲真创建新链表，通过不断拆解这两个链表合为一个， \color{red}{此处创建新链表菲真创建新链表，通过不断拆解这两个链表合为一个，} 此处创建新链表菲真创建新链表，通过不断拆解这两个链表合为一个，
因此要格外注意保存下一个节点和尾节点的 n e x t 为 N U L L \color{red}{因此要格外注意保存下一个节点和尾节点的next为NULL} 因此要格外注意保存下一个节点和尾节点的next为NULL
//8.链表分割/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/classPartition{public: ListNode*partition(ListNode* pHead,int x){//创建两个带哨兵位的空链表 ListNode* lessHead,* lessTail; lessHead = lessTail =(ListNode*)malloc(sizeof(ListNode)); ListNode* greatHead,* greatTail; greatHead = greatTail =(ListNode*)malloc(sizeof(ListNode)); ListNode* pcur = pHead;while(pcur){if(pcur->val < x){ lessTail->next = pcur; lessTail = lessTail->next;}else{ greatTail->next = pcur; greatTail = greatTail->next;} pcur = pcur->next;}//大链表尾节点的next指针置为NULL(避免链表成环) greatTail->next =NULL;//大小链表首尾相连 lessTail->next = greatHead->next; ListNode* ret = lessHead->next;free(lessHead);free(greatHead);return ret;}};
在这里插入图片描述

链表的回文结构

题目链接↓
链表的回文结构

在这里插入图片描述


题目讲解↓

思路1:创建数组(大小900)，遍历链表将节点的值依次存储在数组中，若数组为回文结构，则链表为回文结构
思路2:找链表中间节点，将中间节点作为新链表的头节点，反转链表遍历原链表和反转后链表节点的值是否相等
中间节点->快慢指针
反转链表->三指针法
前面都讲过
  • 思路1
//9.链表的回文结构 bool chkPalindrome(ListNode* A){int arr[900]={0};//遍历链表，将链表中节点的值依次存储到数组中 ListNode* pcur = A;int i =0;while(pcur){ arr[i++]= pcur->val; pcur = pcur->next;}//判断数组是否为回文结构int left =0, right = i -1;while(left < right){if(arr[left]!= arr[right])return false; left++; right--;}return true;}
在这里插入图片描述
  • 思路2
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/classPalindromeList{public://找中间节点structListNode*middleNode(structListNode* head){//创建快慢指针 ListNode* slow = head; ListNode* fast = head;while(fast !=NULL&& fast->next !=NULL)//用到短路（方向不能反，否则空指针解引用）{ slow = slow->next; fast = fast->next->next;}return slow;}//反转链表structListNode*reverseList(structListNode* head){if(head ==NULL)//需要处理一下特殊情况{returnNULL;}//创建三个指针 ListNode* n1,* n2,* n3; n1 =NULL, n2 = head, n3 = n2->next;while(n2){ n2->next = n1; n1 = n2; n2 = n3;if(n3){ n3 = n3->next;}}return n1;}boolchkPalindrome(ListNode* A){//1.找中间节点 ListNode* mid =middleNode(A);//2.反转以中间节点为头的链表  ListNode* right =reverseList(mid);//3.遍历原链表和反转后的链表，比较节点的值是否相等 ListNode* left = A;while(right){if(left->val != right->val)returnfalse; left = left->next; right = right->next;}returntrue;}};

用到的都是前面讲的方法

在这里插入图片描述

相交链表

题目链接↓
相交链表

在这里插入图片描述

题目讲解↓

思路：求两个链表的长度，长链表先走长度差步，长短链表开始同步遍历，找相同的节点两个链表的尾节点相同，两个链表一定相交

不相交

在这里插入图片描述

先了解相交链表的几种情况

在这里插入图片描述
//10.相交链表typedefstructListNode ListNode;structListNode*getIntersectionNode(structListNode* headA,structListNode* headB){//求链表的长度 ListNode* pa = headA; ListNode* pb = headB;int sizeA =0, sizeB =0;while(pa){++sizeA; pa = pa->next;}while(pb){++sizeB; pb = pb->next;}//求长度差int gap =abs(sizeA - sizeB);//求绝对值//定义长短链表（假设法） ListNode* shortList = headA; ListNode* longList = headB;if(sizeA > sizeB){ longList = headA; shortList = headB;}//让长链表先走gapwhile(gap--){ longList = longList->next;}//shortList longList在同一起跑线while(shortList)//或者用while(longList){if(shortList == longList){return shortList;} shortList = shortList->next; longList = longList->next;}//链表不相交returnNULL;}
在这里插入图片描述

环形链表（快慢指针）

环形链表I

题目链接↓
环形链表I

在这里插入图片描述

题目讲解↓

思路：快慢指针，慢指针每次走一步，快指针每次走两步
如果slow和fast指向同一个节点，说明链表带环
typedefstructListNode ListNode; bool hasCycle(structListNode* head){//创建快慢指针 ListNode* slow = head; ListNode* fast = head;while(fast && fast->next){ slow = slow->next; fast = fast->next->next;if(slow == fast){//相遇return true;}}//链表不带环return false;}
在这里插入图片描述
  • 思考1：为什么快指针每次⾛两步，慢指针⾛⼀步可以相遇，有没有可能遇不上，请推理证明！

slow⼀次⾛⼀步，fast⼀次⾛2步，fast先进环，假设slow也⾛完⼊环前的距离，准备进环，此时fast和slow之间的距离为N，接下来的追逐过程中，每追击一次，他们之间的距离缩小1步追击过程中fast和slow之间的距离变化：

因此，在带环链表中慢指针走⼀步，快指针走两步最终⼀定会相遇。
  • 思考2：快指针⼀次走3步，走4步，…n步行吗?
step1:
按照上⾯的分析，慢指针每次⾛⼀步，快指针每次⾛三步，此时快慢指针的最⼤距离为N，接下来的
追逐过程中，每追击⼀次，他们之间的距离缩⼩2步
追击过程中fast和slow之间的距离变化：
分析:
1、如果N是偶数，第⼀轮就追上了
2、如果N是奇数，第⼀轮追不上，快追上，错过了，距离变成-1，即C-1，进⼊新的⼀轮追击
a、C-1如果是偶数，那么下⼀轮就追上了
b、C-1如果是奇数，
那么就永远都追不上
总结⼀下追不上的前提条件：
N是奇数，C是偶数
step2:

假设：

环的周长为 C，头结点到slow结点的长度为
L，slow走一步，fast走三步，当slow指针入环后，slow和fast指针在环中开始进行追逐，假设此时fast指针已经绕环 x 周。

在追逐过程中，快慢指针相遇时所走的路径长度：

• fast：L + xC + C - N • slow：L 由于慢指针走一步，快指针要走三步，因此得出：3 *{慢指针路程} =
{快指针路程}，即：

3L = L + xC + C - N

化简得：

2L = (x + 1)C - N

对上述公式继续分析：由于偶数乘以任何数都为偶数，因此 2L 一定为偶数，则可推导出可能的情况：

• 情况1：偶数 = 偶数 - 偶数

• 情况2：偶数 = 奇数 - 奇数

由step1中（1）得出的结论，如果 N 是偶数，则第一圈快慢指针就相遇了。 由step1中（2）得出的结论，如果 N
是奇数，则fast指针和slow指针在第一轮的时候套圈了，开始进行下一轮的追逐；当 N 是奇数，要满足以上的公式，则 (x+1)C
必须也要为奇数，即 C 为奇数，满足（2）a中的结论，则快慢指针会相遇。 因此，step1中的 N 是奇数，C 是偶数
不成立，既然不存在该情况，则快指针一次走3步最终一定也可以相遇。 快指针一次走4、5……步最终也会相遇，其证明方式同上。
typedefstructListNode ListNode; bool hasCycle(structListNode* head){ ListNode* slow,* fast; slow = fast = head;while(fast && fast->next){ slow = slow->next;int n =3;//fast每次⾛三步while(n--){if(fast->next) fast = fast->next;elsereturn false;}if(slow == fast){return true;}}return false;}
在这里插入图片描述

环形链表II

题目链接↓
环形链表II

在这里插入图片描述

题目讲解↓

思路：快慢指针，在环里一定会相遇
相遇点到入环节点的距离 == 头结点到入环节点的距离
//IItypedefstructListNode ListNode;structListNode*detectCycle(structListNode* head){//创建快慢指针 ListNode* slow = head; ListNode* fast = head;while(fast && fast->next){ slow = slow->next; fast = fast->next->next;if(slow == fast){//相遇点---找入环节点（相遇点到入环节点的距离 == 头结点到入环节点的距离） ListNode* pcur = head;while(pcur != slow){ pcur = pcur->next; slow = slow->next;}return pcur;}}//链表不带环returnNULL;}
在这里插入图片描述
  • 思考为什么相遇点到入环节点的距离 = = 头结点到入环节点的距离 思考为什么相遇点到入环节点的距离 == 头结点到入环节点的距离 思考为什么相遇点到入环节点的距离==头结点到入环节点的距离

说明:

H为链表的起始点，E为环入口点，M为判环时的相遇点

设:

环的长度为 R，H到E的距离为 L，E到M的距离为 X，则：M到E的距离为 R-X 在判环时，快慢指针相遇时所走的路径长度：

• fast：L + X + nR • slow：L + X 注意:当慢指针进入环时，快指针可能已经在环中绕了n圈了，n至少为1 因为：快指针先进环走到M的位置，最后又在M的位置与慢指针相遇慢指针进环之后，快指针肯定会在慢指针走一圈之内追上慢指针 因为：慢指针进环后，快慢指针之间的距离最多就是环的长度，而两个指针在移动时，每次它们之间的距离都缩减一步，因此在慢指针移动一圈之前快指针肯定是可以追上慢指针的，而快指针速度是慢指针的两倍，因此有如下关系：

2 *(L+X) = L+X + nR

化简得：

L+X = nR

L = nR - X

进一步变形：

L = (n-1)R + (R-X)

（n为1,2,3,4,……，n的大小取决于环的大小，环越小n越大）

极端情况下，假设n=1，此时：

L = R - X

代码仓库

仓库地址
感谢大佬们三连，你的鼓励就是对我创作的激励！！！ \color{purple}{感谢大佬们三连，你的鼓励就是对我创作的激励！！！} 感谢大佬们三连，你的鼓励就是对我创作的激励！！！

Read more

Flutter 三方库 web_scraper 轻量级网页抓取核心适配进阶：精通跨端选择器表达式无头浏览器代理、极限提取残缺数据接口网格实现鸿蒙万物互联泛信息-适配鸿蒙 HarmonyOS ohos

Flutter 三方库 web_scraper 轻量级网页抓取核心适配进阶：精通跨端选择器表达式无头浏览器代理、极限提取残缺数据接口网格实现鸿蒙万物互联泛信息-适配鸿蒙 HarmonyOS ohos

欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.ZEEKLOG.net Flutter 三方库 web_scraper 轻量级网页抓取核心适配进阶：精通跨端选择器表达式无头浏览器代理、极限提取残缺数据接口网格实现鸿蒙万物互联泛信息即时采集 前言 在 OpenHarmony 应用开发中，我们并非总能获得完美的后端 API。当我们希望在鸿蒙应用中聚合一些公开的技术资讯、天气指数或是论坛热帖，但对方并未提供标准化 JSON 接口时，通过抓取网页（Web Scraping）获取结构化数据成了唯一的出路。web_scraper 库为 Flutter 开发者提供了一套基于 CSS 选择器的极简网页爬虫方案。本文将实战介绍如何在鸿蒙端利用该库构建一个高效的信息采集底座。 一、原直线性 / 概念介绍 1.1 基础原理/概念介绍 web_scraper 的核心逻辑是基于 HTTP 内容请求与 HTML DOM 树的解析映射。

By Ne0inhk
离开舒适区之后：从三年前端到 CS 硕士——我在韩国亚大读研的得失

离开舒适区之后：从三年前端到 CS 硕士——我在韩国亚大读研的得失

过去一年多，我做了一个挺重要的决定：辞职，去韩国留学读研。 这段时间我几乎没怎么学习新的前端内容，但也没有停下来。我在韩国亚洲大学完成了计算机科学与技术（大数据）硕士的学习，在高强度的节奏里重新建立了自己的方法，也因为持续写博客获得了一些机会，担任本科 Web 实训课讲师。现在这段留学告一段落，我也准备重新回到前端领域，把这段经历当作一份额外的积累带回去。这篇复盘主要是想把这一路的收获、疲惫和一些值得记住的瞬间记录下来，留给未来的自己，也分享给路过的你。 文章目录 * 1、写在前面：我为什么会从前端转去读研 * 2、留学生活的关键词：卷、AI、被看见以及校庆的“放开玩” * 3、我的“结果卡片” * 4、得：这一年半我真正收获的东西 * 5、失：我付出的代价 * 6、期末周：我经历过的“高强度交付周” * 7、前端三年经验，如何在读研里“迁移复用” * 8、我在韩国的学习系统：

By Ne0inhk

OpenClaw Webhook 详解：完整指南

Webhook 是将 OpenClaw 从“聊天助手”快速转变为“响应式系统”的最佳方式。无需等待您主动发送消息，GitHub 可以在 PR 提交时通知 OpenClaw，Stripe 可以在支付失败时通知 OpenClaw，n8n 也可以按计划通知 OpenClaw。OpenClaw 会接收这些传入事件，并将其转换为代理运行或轻量级唤醒操作，然后将结果路由回您实际使用的任何渠道。 本文重点介绍 OpenClaw 网关上的 HTTP Webhook。OpenClaw 中还有另一种东西，在一些文档和配置中也被称为“钩子”。这些是网关内部的事件钩子，当本地生命周期事件触发时运行。它们也很有用，但 Stripe 或 GitHub 与服务器通信的方式并非通过它们。 如果您的 OpenClaw 实例是刚刚部署在 VPS 上，并且您仍然使用 SSH 进行基本操作，那么首先要确保网关稳定，

By Ne0inhk
【前端实战】从 try-catch 回调到链式调用：一种更优雅的 async/await 错误处理方案

【前端实战】从 try-catch 回调到链式调用：一种更优雅的 async/await 错误处理方案

目录 【前端实战】从 try-catch 回调到链式调用：一种更优雅的 async/await 错误处理方案 一、问题背景：async/await 真的解决了一切麻烦吗？ 二、真实业务场景下的痛点 1、错误需要“分阶段处理” 2、try-catch 的引入打破了 async/await 的链式范式 三、借鉴 Go、Rust 语言特性，错误也是一种结果 1、错误优先风格替代 try-catch 2、封装一个 safeAsync 工具函数 四、进阶版 safeAsync 函数设计 五、结语         作者：watermelo37         ZEEKLOG优质创作者、华为云云享专家、阿里云专家博主、腾讯云“

By Ne0inhk