企业官网建设流程全解析

域名备案中网站可以开通,html网站开发需要什么软件,十佳网站,piwigo wordpress一.快慢指针的运用 1.找到链表的中间节点#xff1a; 对于这题#xff0c;我们可以选择创建一个整形c以遍历链表的方式记录链表的长度#xff0c;然后再让头节点位置的指针向前走c/2次就得到了我们想要的节点。 但它还有一种更简单的做法(快慢指针)#xff1a; 我们可以先…一.快慢指针的运用1.找到链表的中间节点对于这题我们可以选择创建一个整形c以遍历链表的方式记录链表的长度然后再让头节点位置的指针向前走c/2次就得到了我们想要的节点。但它还有一种更简单的做法(快慢指针)我们可以先定义两个与链表节点同类型的指针slowfast并让它们都指向头节点(head)。然后为了让这两个指针指向后面的节点建立一个循环使fast指针每次向后移动两个节点slow指针每次向后移动一个节点这样我们就建立了这两个指针的路程关系L(fast) 2 * L(slow)。可以得到当fast指向链表末尾的时候slow才走它一半的距离即走到中间节点。注意链表长度的奇偶性会影响fast的最终指向偶fast应该指向NULL奇fast应该指向最后一个节点因此我们就可以得到循环条件while(fast fast -next)structListNode*middleNode(structListNode*head){LTN*slowhead;LTN*fasthead;while(fastfast-next){slowslow-next;fastfast-next-next;}returnslow;}特别注意在while(fast fast -next)中fast和fast-next位置不可颠倒因为当链表长度为偶数时fast指向NULL不能对NULL进行解引用。题目https://leetcode-cn.com/problems/middle-of-the-linked-list/description/2.找到链表的倒数第k个节点这里也是运用快慢指针但相比于上面快慢指针的起始位置相同而速度不同这里的是起始位置不同速度相同。设置slow、fast指针先让fast指针走k步然后再让slow与fast每次一步的速度同时开始向前走。这样保证了两个指针的相对位置保持k不变当fast为空时slow指向倒数第k个节点。intkthToLast(structListNode*head,intk){structListNode*fasthead,*slowhead;while(k--){fastfast-next;}while(fast){fastfast-next;slowslow-next;}returnslow-val;}题目https://leetcode.cn/problems/kth-node-from-end-of-list-lcci/二.链表的回文结构所谓回文就是一组数据从前往后读和从后往前读的结果都一样。如果我们不考虑空间复杂度可以这样做遍历链表以int c 记录链表的长度再创建一个长度为c元素类型为所要比较的链表中的数据类型再遍历链表将链表中的数据存如数组中最后用判断数组是否回文的方法判断该链表是否回文。大家可以试着写写以上思想的代码我接下来为大家带来一个十分巧妙的思路。以原链表为1-2-3-2-1 为例第一步找到中间节点mid第二步将mid及其之后的代码倒置:1-2-1-2-3;第三步设置两个指针分别指向头节点head和中间节点mid最后让两个指针每走一步比较一下相等则继续不等则返回false。ListNode*get_mid(ListNode*a)//找中间节点{ListNode*slowa;ListNode*fasta;while(fast){fastfast-next;slowslow-next;if(!fast)break;fastfast-next;}returnslow;}ListNode*invert(ListNode*M)//倒置{ListNode*newheadNULL;ListNode*curM;while(cur){ListNode*nextcur-next;cur-nextnewhead;newheadcur;curnext;}returnnewhead;}boolchkPalindrome(ListNode*A){// write code hereListNode*mid;midget_mid(A);ListNode*rmid;rmidinvert(mid);ListNode*pcurA;while(pcurrmid){if(pcur-val!rmid-val)returnfalse;pcurpcur-next;rmidrmid-next;}returntrue;}题目https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId49tqId29370rp1ru/activity/ojqru/ta/2016test/question-ranking三.单链表的相交判断两条单链表是否相交可以看出如果两条单链表相交它们的尾节点一定相同。因此我们可以通过判断尾节点是否相同来判断它们是否相交。我们在加上一个条件找出链表相交处的节点我们先用以上方法判断链表是否相交如果不相交就返回NULL相交则继续设置两个指针AB分别指向两个链表的头节点。试想如果这两条链表长度相等我们同时让AB从头开始遍历它们个自对应的链表每走一步对AB的地址进行比较自然可以得到相交的节点。但如果它们长度不一呢很显然如果同时从头开始的话它们会彼此错过一定找不到相交的节点。所以我们要想办法让AB遍历前距相交节点的距离相等要怎么做呢1.在判断链表是否相交的同时记录下两条链表的长度structListNode*AheadA;structListNode*BheadB;inta0,b0;while(A-next){AA-next;a;}while(B-next){BB-next;b;}if(A!B)//相交链表的最后一个节点一定相同{returnNULL;}然后我们比较ab指向更长链表的节点先走a-b的绝对值步intlenabs(a-b);//计算两链表的长度差structListNode*shortlistheadA;structListNode*longlistheadB;//假设法找出长短链表if(ab){shortlistheadB;longlistheadA;}while(len--){longlistlonglist-next;}这里运用了假设法先假设链表A更短B更长然后再用if得到真正的长短链表。注这里不需要知道AB谁更长了长链表已经用 longlist表示短链表已经用shortlist表示。最后让两个longlist与shortlist同时开始一步一步的走while(longlist){if(longlistshortlist)break;longlistlonglist-next;shortlistshortlist-next;}总代码structListNode*getIntersectionNode(structListNode*headA,structListNode*headB){structListNode*AheadA;structListNode*BheadB;inta0,b0;while(A-next){AA-next;a;}while(B-next){BB-next;b;}if(A!B)//相交链表的最后一个节点一定相同{returnNULL;}intlenabs(a-b);//计算两链表的长度差structListNode*shortlistheadA;structListNode*longlistheadB;//假设法找出长短链表if(ab){shortlistheadB;longlistheadA;}while(len--){longlistlonglist-next;}while(longlist){if(longlistshortlist)break;longlistlonglist-next;shortlistshortlist-next;}returnlonglist;}四.判断链表是否成环关于这个问题我们可以创建一对速度比为12的快慢指针如果该链表不成环则fast或fast-next最终指向NULL如果成环fast会在环内反复运动当slow进环时fast开始追赶slow每一次循环它们的距离会缩小1因此最终它们一定能相遇。boolhasCycle(structListNode*head){structListNode*slowhead;structListNode*fasthead;while(fastfast-next){slowslow-next;fastfast-next-next;if(slowfast)returntrue;}returnfalse;}题目https://leetcode-cn.com/problems/linked-list-cycle/description/我们不妨大胆猜测一下fast可以取345……吗我们拿三来举例子如图我们令链表不成环部分长L成环部分长C当slow准备进环时slow与fast相距N-C,此时slowLfast3L L x * C Nx为fast走的圈数fast距slowC - Nfast与slow的相对速度2i.如果C-N为偶数(C - N) % 2 0fast一定能追上slowii.如果C-N为奇数(C - N) % 2 ! 0fast第一次会超过slow二者距离变为C-1ii.1 如果C-1为偶fast一定能追上slowii.2 如果C-1为奇fast会第二次超过slow距离再次变为C-1这种情况下fast不可能追上slow。因此我们可以得到一些小结论i. C-N为偶fast与slow会相遇ii. C - N为奇C-1为偶会相遇C-1为奇不会相遇等量关系2L x * C N (x 1) * C - (C - N)很显然2L是一个偶数偶数 偶数-偶数 偶数 奇数 - 奇数我们可以从这里入手。1.如果x1为偶数(x1)*C必为偶(C - N)为偶fast会与slow相遇2.如果x1为奇数i. C为偶(C - N)为偶相遇ii.C为奇(C - N)为奇相遇由此可以推导出即使fast速度为3它们依然能够相遇。事实上当fast 2时fast总能追上slow但我的能力有限具体证明大家可以自行了解。2.我们再提高点难度如果我们要找到成环的起始点该怎么写(()里的是速度先说结论slow(1),fast(2)设一个指针meet它指向slow与fast相遇的那个节点。然后我们让slow(1)从头开始走同时meet(1)从相遇点开始走它们会在成环起始节点相遇。structListNode*detectCycle(structListNode*head){if(!head)returnNULL;structListNode*slowhead;structListNode*fasthead;structListNode*curhead;while(fastfast-next){slowslow-next;fastfast-next-next;if(slowfast){curslow;break;}}if(!fast||!fast-next)returnNULL;slowhead;while(slow!cur){slowslow-next;curcur-next;}returncur;}题目https://leetcode-cn.com/problems/linked-list-cycle-ii/description/那为什么呢如图我们设相遇点距成环起始节点(C-N).从slow与fast开始走到相遇的过程注意slow进环后在其走一圈之前fast一定能追上它因为slow与fast的相对速度为1它们不可能错过如果在相遇前slow走了1圈fast就走了2圈这显然不可能成立。slow:L Nfast:L xC N 2(L N)等量关系L xC - N (x - 1)*C C- Nmeet和slow 同时开始走S(meet) S(slow) L (x - 1)*C C- N可以看出meet与slow同时到达了成环起始点。五.链表的深拷贝题目https://leetcode-cn.com/problems/copy-list-with-random-pointer/description/每个节点内有/** * Definition for a Node. * struct Node { * int val; * struct Node *next; * struct Node *random; * }; */我们可以看出这题的难点在random指向的节点位于链表中的什么位置。这里有一个非常巧妙的思路1.我们可以在每个原节点的后面创建一个所含内容(除random外)与其一样的节点并将random置为NULL。2.对复制的random进行赋值i. 如果原链表中的一个节点中的random为NULL则其对应的复制节点的random也应为NULLii. 如果不为空如果原节点中的random指向的节点在原链表中是第pos(相对与头节点)个那么该节点所对于的复制节点中的random应该指向复制链表中的第pos个。例如上图中B-random A, 那么B’-random A’这时候我们将复制节点放在原节点后面的行为就极大的便利了这一步B’-random A’等价于B-next-random B-random-next//处理复制节点的randomcurhead;//指向原链表的头节点structNode*newheadcur-next;structNode*newcurnewhead;//指向复制链表的头节点while(cur){if(cur-random)newcur-randomcur-random-next;elsenewcur-randomNULL;curnewcur-next;if(cur)newcurcur-next;}3.最后复制节点中只有next需要修改也就是说我们这里需要把复制链表分离出来//分离两个链表curhead;newcurnewhead;while(cur){cur-nextnewcur-next;curcur-next;if(cur){newcur-nextcur-next;newcurnewcur-next;}elsenewcur-nextNULL;}总代码structNode*copyRandomList(structNode*head){if(!head)returnNULL;structNode*curhead;while(cur)//将原链表节点的复制节点放在原链表节点后这样找到random后可迅速找到复制后对应的random{structNode*newnode(structNode*)malloc(sizeof(structNode));newnode-nextcur-next;newnode-valcur-val;newnode-randomNULL;cur-nextnewnode;curnewnode-next;}//处理复制节点的randomcurhead;//指向原链表的头节点structNode*newheadcur-next;structNode*newcurnewhead;//指向复制链表的头节点while(cur){if(cur-random)newcur-randomcur-random-next;elsenewcur-randomNULL;curnewcur-next;if(cur)newcurcur-next;}//分离两个链表curhead;newcurnewhead;while(cur){cur-nextnewcur-next;curcur-next;if(cur){newcur-nextcur-next;newcurnewcur-next;}elsenewcur-nextNULL;}returnnewhead;}