手机网站设计教育类模板,夏天做那些网站致富,大连住建部官网,重庆公司章程如何查询下载创作不易#xff0c;友友们给个三连呗#xff01;#xff01; 本文为经典算法OJ题练习#xff0c;大部分题型都有多种思路#xff0c;每种思路的解法博主都试过了#xff08;去网站那里验证#xff09;是正确的#xff0c;大家可以参考#xff01;#xff01;
一、移… 创作不易友友们给个三连呗 本文为经典算法OJ题练习大部分题型都有多种思路每种思路的解法博主都试过了去网站那里验证是正确的大家可以参考
一、移除元素力扣
经典算法OJ题移除元素
思路1遍历数组找到一个元素等于val就把后面的所有元素往前挪类似顺序表实现中的指定位置删除
//思路1遍历数组找到一个元素等于val就把后面的所有元素往前挪类似顺序表实现中的指定位置删除
int removeElement(int* nums, int numsSize, int val)
{for (int i 0; i numsSize; i)//用来遍历{if (nums[i] val)//要挪动而且是从前往后挪{for (int j i; j numsSize - 1; j)nums[j] nums[j 1];//从前往后挪numsSize--;//挪完长度-1i--;//挪动后新的数据还在原来的位置所以不能让i往前走}}return numsSize;
}
思路2双指针法利用双指针第一个指针引路第二个指针存放想要的元素不等于val的元素较优
//思路2双指针法利用双指针第一个指针引路第二个指针存放想要的元素不等于val的元素
int removeElement(int* nums, int numsSize, int val)
{int src 0;//用来探路src即原操作数int dst 0;//用来存放想要的数据dst即目标操作数while (src numsSize){if (nums[src] val){src;//找到val就src走}else{nums[dst] nums[src];//dst接收想要的数据//找不到就两个都走dst;src;}}//此时dst恰好就是数组的新长度return dst;
}
二、合并两个有序数组力扣
经典算法OJ题合并两个有序数组 思路1num2全部存储到num1中再统一进行排序qsort
int int_cmp(const void* p1, const void* p2)//比较方法
{return (*(int*)p1 - *(int*)p2);//返回值来影响qsort
}void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{int i m;//指向数组1后面的空位置int j 0;//指向数组2while (i m n){nums1[i] nums2[j];i;j;}//循环结束说明插入完成使用快速排序qsort(nums1, m n, sizeof(int), int_cmp);
}
思路2合并的时候顺便排序利用3个指针l1用来遍历数组1l2用来遍历数组2比大小之后的数据用l3记录。较优
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{int l1m-1;//从1数组的最后一个有效数据往前int l2n-1;//从2数组的最后一个有效数据往前int l3nm-1;//从1数组的最后一个元素开始往前while(l10 l20)//l1和l2其中一个遍历完就得跳出循环{//从后往前比大小
if(nums1[l1]nums2[l2])nums1[l3--]nums1[l1--];
elsenums1[l3--]nums2[l2--];}//循环结束后有两种情况一种是l1先遍历完此时l2要接着插进去//另一种是l2先遍历完此时l1就不需要处理了while(l20)nums1[l3--]nums2[l2--];
}
三、移除链表元素力扣
经典算法OJ题移除链表元素 思路1遍历原链表遇到val就删除类似单链表的指定位置删除
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val)
{//考虑头节点就是val的情况while(head!NULLhead-valval)headhead-next;//此时头节点不可能是val//当链表为空if(headNULL)return head;//当链表不为空时ListNode*pcurhead;//用来遍历链表ListNode*prevNULL;//用来记录前驱结点while(pcur){//当找到val时if(pcur-valval){prev-nextprev-next-next;//前驱结点指向pucr的下一个结点free(pcur);//删除的结点被释放pcurprev-next;//继续指向新的结点}//没找到val时else{prevpcur;//往后走之前记录前驱结点pcurpcur-next;//pcur往前遍历}}return head;
}
思路2定义一个不带头新链表将不为val的结点尾插进去
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val)
{ListNode*pcurhead;//用来遍历链表//定义新链表的头尾指针ListNode*newheadNULL;//用来记录头ListNode*newtailNULL;//用来尾插新链表while(pcur)
{if(pcur-val!val)//不满足val则插入到新链表{//一开始链表是空的if(newheadNULL)newheadnewtailpcur;//链表不为空了开始尾插else{newtail-nextpcur;//尾插newtailnewtail-next;//尾插后向后挪动}}pcurpcur-next;//pcur要遍历往后走
}
//插入完后要加NULL还要避免newtail是空的情况
if(newtail)
newtail-nextNULL;
return newhead;
}
思路3给原链表创造一个哨兵结点然后遍历遇到val就删和思路1比较多了一个哨兵稍优于思路1
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val)
{ListNode*newhead(ListNode*)malloc(sizeof(ListNode));//创建一个新的哨兵节点newhead-nexthead;//哨兵接头ListNode*pcurhead;//用来遍历链表ListNode*prevnewhead;//记录前驱结点
while(pcur)
{//遇到了开始删除
if(pcur-valval)
{prev-nextpcur-next;free(pcur);pcurprev-next;
}
//如果没遇到val都往后走
else
{prevpcur;pcurpcur-next;
}
}
//循环结束删除完成
ListNode*retnewhead-next;//释放哨兵结点前记住需要返回的结点
free(newhead);
newheadNULL;
return ret;
}
思路4定义一个带头新链表将不为val的结点尾插进去和思路2相比较多了一个哨兵较优
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val)
{ListNode*newhead,*newtail;newheadnewtail(ListNode*)malloc(sizeof(ListNode));//创建一个新的哨兵节点ListNode*pcurhead;//用来遍历链表while(pcur){if(pcur-val!val){//找打不为val的值 开始尾插newtail-nextpcur;newtailnewtail-next;}pcurpcur-next;//没找到就往后找}newtail-nextNULL;ListNode*retnewhead-next;//释放哨兵时记住返回值free(newhead);newheadNULL;return ret;
}
四、反转链表力扣
经典算法OJ题反转链表 思路1利用带头单链表头插法建立一个新的带头结点的单链表L,扫描head链表的所有结点每扫描一个结点就创造一个s结点并将值赋给s结点然后头插法插入新链表L中得到的就是逆序的head链表 typedef struct ListNode ListNode;ListNode*BuyNode(int x)//封装创建新结点的函数{ListNode*newnode(ListNode*)malloc(sizeof(ListNode));newnode-nextNULL;newnode-valx;return newnode;}
struct ListNode* reverseList(struct ListNode* head)
{ListNode*pcurhead;//用来遍历ListNode*newheadBuyNode(-1);//创建哨兵结点ListNode*tempNULL;//充当临时变量while(pcur)
{tempBuyNode(pcur-val);//创建新结点接收pur的值//头插temp-nextnewhead-next;newhead-nexttemp;//pcur往后走pcurpcur-next;//pcur往后走
}
ListNode*retnewhead-next;//哨兵位释放之前保存头节点
free(newhead);
newheadNULL;
return ret;
}
思路2利用带头单链表头插法建立一个新的带头结点的单链表L,扫描head链表的所有结点每扫描一个结点就头插法插入新链表L中得到的就是逆序的head链表相比思路1多了个哨兵稍优于思路1 typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head)
{//如果链表为空if(headNULL)return head;//如果链表不为空ListNode*newhead,*newtail;//一个哨兵一个记录尾巴方便后面置NULLnewhead(ListNode*)malloc(sizeof(ListNode));//创建哨兵结点newhead-nexthead;//哨兵和原来的头节点连接起来newtailhead;//newtail记住一开始的head方便后面连接NULLListNode*pcurhead-next;//pcur用来遍历(从第二个)ListNode*tempNULL;//用来记录下一个遍历点while(pcur){temppcur-next;//连接前先记住下一个结点的位置//头插 插在哨兵结点和原来头结点的中间newhead-nextpcur;pcur-nexthead;headpcur;//头插进来的成为哨兵结点后面的新头pcurtemp;//pcur从原先链表的下一个结点开始继续遍历}newtail-nextNULL;//要记得给尾巴结点连接NULLfree(newhead);newheadNULL;return head;
}
思路3利用不带头链表头插法扫描head链表的所有结点每扫描一个结点就头插法插入新链表L中得到的就是逆序的head链表(较优)
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head)
{//如果链表为空if(headNULL)return head;//如果链表不为空ListNode*pcurhead-next;//用来遍历ListNode*ptailhead;//用来记录尾巴方便后面置NULLListNode*temp;//记录遍历的结点while(pcur){temppcur-next;//头插到head前面
pcur-nexthead;
headpcur;
pcurtemp;}ptail-nextNULL;return head;
}
思路4利用3个指针分别记录前驱结点、当前结点、后继结点改变原链表的指针指向(最优) typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head)
{//链表为空的时候if(headNULL)return head;//链表不为空的时候创建3个指针分别指向前驱、当前、后继结点
ListNode*p1,*p2,*p3;
p1NULL;//前驱
p2head;//当前
p3head-next;//后继
while(p2)
{//改变指向
p2-nextp1;
//向后挪动
p1p2;
p2p3;
//考虑p3为NULL的时候
if(p3)
p3p3-next;
}
return p1;
}
五、合并两个有序链表力扣
经典算法OJ题合并两个有序链表 思路1创建一个哨兵节点双指针判断两组数据的大小因为是把 list2 的节点插入 list1 所以只要当 list1 指向的数大于 list2 的数就把当前 list2 节点插入 list1 的前面。循环判定条件只要双指针中有一个为空就跳出循环即有一个指针到了节点末端。若 list1 先结束表示剩下 list2 的数都比 list1 里的数大直接把 list2 放到 list1后即可若 list2 先结束即表示已经合并完成。
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{ListNode*newhead(ListNode*)malloc(sizeof(ListNode));//创建一个新的哨兵结点newhead-nextlist1;//哨兵点与list1相连接ListNode*p1list1;//利用p1遍历链表1ListNode*p2list2;//利用p2遍历链表2ListNode*prevnewhead;//prev记录前驱结点ListNode*tempNULL;//充当临时变量,暂时保存list2的指向while(p1p2)//p1和p2有一个为NULL了就必须跳出循环{
if(p1-valp2-val)//list2插入list1该元素前面
{tempp2-next;//记住p2指针的遍历点//尾插prev-nextp2;p2-nextp1;//尾插完成往前走prevp2;p2temp;
}
//找不到时prev和p1都往后走
else
{p1p1-next;prevprev-next;
}}
//跳出循环后有两种可能一种是p1先为NULL一种是p2先为NULL
//此时prev恰好走到尾结点
//如果p2为NULL说明已经结束如果p1为NULL此时尾插p2在prev后面
if(p1NULL)
prev-nextp2;
ListNode*retnewhead-next;//哨兵位要释放返回前要记录newhead-next
free(newhead);
newheadNULL;
return ret;
}
思路2定义一个带头新链表方便返回两个指针分别指向两组数组逐个比较较小的尾插到新的链表中循环判断条件只要有一个指针为NULL就跳出循环无论是 list1 结束还是 list2 结束只需要把剩下的部分接在新链表上即可。较优
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{ListNode*newhead,*newptail;newhead newptail(ListNode*)malloc(sizeof(ListNode));//创建一个新的哨兵结点//newptail是用来尾插的ListNode*p1list1;//利用p1遍历链表1ListNode*p2list2;//利用p2遍历链表2while(p1p2)//p1和p2有一个为NULL了就必须跳出循环{
if(p1-valp2-val)
{newptail-nextp1;//尾插newptailnewptail-next;//插入后newptail往后走p1p1-next;//插入后p1往后走
}
else
{newptail-nextp2;//尾插newptailnewptail-next;//插入后newptail往后走p2p2-next;//插入后p2往后走
}}
//跳出循环后有两种可能一种是p1先为NULL一种是p2先为NULL
//在newtail后面插入不为NULL的链表。
newptail-next(p1NULL?p2:p1);
ListNode*retnewhead-next;//哨兵位要释放返回前要记录newhead-next
free(newhead);
newheadNULL;
return ret;
}
六、链表的中间结点力扣
经典算法OJ题链表的中间结点 思路1统计链表中结点的个数然后除以2找到中间结点
typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head)
{int count0;//用来记录总共的结点数量ListNode*pcurhead;//用来遍历while(pcur){pcurpcur-next;count;}//此时计算出count除以2countcount/2;//此时count代表中间结点的位置while(count){headhead-next;count--;}return head;
}
思路2快慢指针法创建两个指针一开始都指向头节点一个一次走一步一个一次走两步当快指针为NULL时慢指针指向的就是中间的位置较优
typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head)
{
ListNode*fast,*slow;
fastslowhead;//都指向头结点
while(fast!NULLfast-next!NULL)//存在一个就得跳出循环
//而且顺序不能反因为与运算符从前往后运算
{fastfast-next-next;//走两步slowslow-next;//走一步
}
//循环结束slow正好指向中间结点
return slow;
}
七、分割链表力扣
经典算法OJ题分割链表 思路1创建一个新链表遍历原链表小的头插大的尾插。
typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x)
{//链表为空if(headNULL)return head;//链表不为空
ListNode*pcur,*newtail;
pcurnewtailhead;//pcur用来遍历 newtail用来尾插
while(pcur)
{ListNode * temppcur-next;if(pcur-valx){
//头插pcur-nexthead;headpcur;//pcur成为新的头}
//尾插else{newtail-nextpcur;newtailnewtail-next;}pcurtemp;//继续遍历
}
newtail-nextNULL;
return head;
}
思路2创建两个新链表遍历原链表大的尾插大链表小的尾插小链表最后合并在一起。
typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x)
{if(headNULL)return head;ListNode*bighead,*bigtail,*smallhead,*smalltail;bigheadbigtail(ListNode*)malloc(sizeof(ListNode));//大链表哨兵smallheadsmalltail(ListNode*)malloc(sizeof(ListNode));//小链表哨兵ListNode*pcurhead;//pcur用来遍历while(pcur){if(pcur-valx)//尾插小链表{smalltail-nextpcur;smalltailsmalltail-next;}else//尾插大链表{bigtail-nextpcur;bigtailbigtail-next;}pcurpcur-next;//继续往下走}//遍历完成连接大小链表smalltail-nextbighead-next;bigtail-nextNULL;ListNode*retsmallhead-next;//记住返回值free(bighead);free(smallhead);return ret;
}
八、环形链表的约瑟夫问题牛客
经典算法OJ题环形链表的约瑟夫问题 思路创建一个不带头的单向链表每逢m就删除
typedef struct ListNode ListNode;
ListNode * BuyNode(int x)//创建结点的函数
{
ListNode *newnode(ListNode *)malloc(sizeof(ListNode));
newnode-nextnewnode;
newnode-valx;
return newnode;
}
int ysf(int n, int m ) {// write code here//创建一个不带头的单向循环链表ListNode *pheadBuyNode(1);//创建一个头节点ListNode *ptailphead;//用来遍历for(int i2;in;i){ptail-nextBuyNode(i);ptailptail-next;}//创建完后要首尾相连ptail-nextphead;ListNode *pcurphead;//pcur用来遍历ListNode *prevNULL;//用来记录前驱结点int count1;//用来数数while(pcur-next!pcur)//结束条件是场上只剩下一个人{if(countm){//指定位置删除prev-nextpcur-next;free(pcur);pcurprev-next;count1;//重新数}else{prevpcur;pcurpcur-next;count;}
}
//此时pcur是场上唯一还在的结点
return pcur-val;
}
九、总结
1、顺序表背景的OJ题较为简单因为顺序表底层是数组有连续存放的特点一方面指针运算偏移比较容易可以多往指针的方向思考另一方面就是我可以根据下标去拿到我想要的元素无论是从前遍历还是从后遍历还是从中间都很方便所以解题思路容易一些而单链表只能通过指向并且非双向的链表想从后面或者中间遍历会比较吃力
2、顺序表背景的题如果涉及到指定位置插入或者是指定位置删除需要大量挪动数据多层for循环比较麻烦有时候可以往指针运算去思考
3、链表背景的题涉及到有关中间结点的一般是快慢指针
4、关于链表的头插如果是两个链表根据情况插入到一个新链表的头插那么创建一个哨兵位结点会比较容易点因为这样可以避免一开始就得换头结点。如果是在原链表的基础上头插因为原链表是存在头节点的这个时候不设哨兵位就会简单点因为可以直接换头。
5、关于链表的尾插一般需要设置一个tail指针往后遍历。
6、关于链表的指定位置插入或删除需要记录前驱结点这个时候需要除了需要考虑头节点为NULL的情况还要考虑链表只有一个结点的情况因为这个时候也没有前驱结点这个时候如果运用哨兵就不需要考虑只有一个结点的情况因为哨兵位可以充当头结点的前驱结点。
7、哨兵链表容易记住起始地址
