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

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

算法王冠上的明珠——动态规划之路径问题(第一篇）

算法王冠上的明珠——动态规划之路径问题(第一篇）

目录 1. 什么叫路径类动态规划 一、核心定义（通俗理解） 二、核心特征（识别这类问题的关键） 2. 动态规划步骤 状态表示 状态转移方程 初始化 填表顺序 返回值 3. 例题讲解 3.1 LeetCode62. 不同路径 3.2 LeetCode63. 不同路径 II 3.3 LeetCodeLCR 166. 珠宝的最高价值 今天我们来聊一聊动态规划的路径类问题。 1. 什么叫路径类动态规划 路径类动态规划是 动态规划的一个重要分支，核心解决 “从起点到终点的路径相关问题”—— 比如 “路径总数”“最短路径长度”“路径上的最大 / 最小和” 等，其本质是通过 “状态递推” 避免重复计算，高效求解多阶段决策的路径问题。 一、

By Ne0inhk
【动态规划】数位DP的原理、模板（封装类）

【动态规划】数位DP的原理、模板（封装类）

本文涉及知识点 C++动态规划 复杂但相对容易理解的解法 上界、下界的位数一样都为N。如果不一样，拆分一样。比如：[10,200]，拆分[10,99]和[100,200]。由于要枚举到 1 ∼ N 1\sim N 1∼N，故实际复杂度是N倍。 动态规划的状态表示 dp[n][m][m1]，n表示已经处理最高n位，m表示上下界状态：0非上下界，1下界，2上界，3上下界。m1是自定义状态。 某题范围是[110,190]，处理一位后：1是上下界，无其它合法状态。处理二位后，11是下界，19是上界， 12 ∼ 18 12

By Ne0inhk
【LeetCode_27】移除元素

【LeetCode_27】移除元素

刷爆LeetCode系列 * LeetCode27题： * github地址 * 前言 * 题目描述 * 题目思路分析 * 代码实现 * 算法代码优化 LeetCode27题： github地址 有梦想的电信狗 前言 本文用C++实现LeetCode 第27题 题目描述 题目链接：https://leetcode.cn/problems/remove-element/ 题目思路分析 目标分析： 1. 将数组中等于val的元素移除 2. 原地移除，意味着时间复杂度为O(n)，空间复杂度为O(1) 3. 返回nums中与val值不同的元素个数 思路：双指针 * src：用于扫描元素，从待扫描元素的第一个开始，因此初始下标为0 * dst：指向数组中，最后一个位置正确的元素的下标，因此初始值为-1 * count：记录赋值的次数，赋值的次数即为数组中与val值不同的元素个数，初始值为0 操作： * nums[

By Ne0inhk
一文彻底搞清楚数据结构之快速排序和归并排序的深入优化

一文彻底搞清楚数据结构之快速排序和归并排序的深入优化

🔥承渊政道：个人主页 ❄️个人专栏: 《C语言基础语法知识》《数据结构与算法初阶》 ✨逆境不吐心中苦,顺境不忘来时路!🎬 博主简介: 前言:前面小编已经介绍八大排序算法的基本思想和实现方法!但关于其中的快速排序和归并排序还有一些细节可以优化!接下来跟着小编来看看快速排序和归并排序的深入优化,学习一下优化完之后,具体在实际中的应用!废话不多说,下面跟着小编的节奏🎵一起学习吧！ 目录 * 1.快速排序性能的关键点分析 * 1.1三路划分算法思想讲解 * 1.2hoare和lomuto和三路划分单趟排序代码分析 * 1.3三种快排单趟排序运⾏结果分析 * 2.排序数组OJ题 * 2.1lomuto的快速排序跑排序数组OJ题 * 2.2hoare的快速排序跑排序数组OJ题 * 2.3三路划分的快速排序跑排序数组OJ题 * 2.4introsort的快速排序跑排序数组OJ题 * 3.外排序介绍 * 3.1创建随机数据⽂件的代码 * 3.2⽂件归并排序思路分析 * 3.3⽂件归并排序代码实现 * 3.4非递归版

By Ne0inhk