百度号注册官网北京seo怎么优化

当前位置： 首页 > news >正文

百度号注册官网,北京seo怎么优化,上海网站建设模版,小瓢虫社区北京网址环形链表 前言一、环形链表二、代码实现三、证明当fast一次走两步#xff0c;slow一次走一步时#xff0c;相遇情况当fast一次走三步#xff0c;slow一次走一步时#xff0c;相遇情况当fast一次走四步#xff0c;slow一次走一步时#xff0c;相遇情况第一种#xff1a;N… 环形链表 前言一、环形链表二、代码实现三、证明当fast一次走两步slow一次走一步时相遇情况当fast一次走三步slow一次走一步时相遇情况当fast一次走四步slow一次走一步时相遇情况第一种N 3kk≥0第二种N 3K 1,K≥0第三种N 3K 2,K≥0 总结 前言 本篇讲解环形链表的解决方法与证明方法 一、环形链表 题目链接https://leetcode.cn/problems/linked-list-cycle/description/ 本题实际有多种解决方法我们在此仅讲解一种能够将空间复杂度控制在O(1)的解法 首先我们观察题目假定这个链表是环形链表的话我们定义一个指针一步一步地往下走那么该指针必然会在环内循环此时如果我们再定义一个指针从起始点开始走那么必然也会进入环并且有几率与前面的指针相遇 这就转化成了我们中学时常见的物理问题——追及问题 追及问题中往往是一者快一者慢那么我们为了分辨便可以使用双指针法定义一个快指针fast一个慢指针slow两者均从起点开始走fast一次走两步即两个结点慢指针一次走一步那么当两者都进入环之后就会在环内循环并且必然会相遇而两者相遇就代表这个链表是环形链表。因为如果这个链表是一个普通的不带环链表那么指针必然会走到空并且快指针fast必然会先慢指针一步走到空 因此我们可以使用双指针法来解决问题 二、代码实现 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode next; };*/ bool hasCycle(struct ListNode head) {struct ListNode low head;if(head NULL)return false;struct ListNode* high head-next;if(high NULL)return false;while(high ! low high ! NULL high-next ! NULL){high high-next-next;low low-next;}if(high high-next)return true;elsereturn false; }三、证明 上面我们提到了可以使用双指针法来解决问题那么我们不免会提出一个疑问为什么快指针fast一次走两步慢指针slow一次走一步一定会相遇它们不会错过吗为什么如果fast一次走三步走四步怎么办 下面我们对这个问题进行讲解、证明 当fast一次走两步slow一次走一步时相遇情况 如图我们先以fast一次走两步slow一次走一步的情况进行证明 当slow进环时fast已经在环里走了一段距离了并且在追及问题中必然是fast追上slow而不是slow追上fast所以此时我们假定两者间的距离为N 因为fast一次走两步slow一次走一步并且fast走的是比slow快的在追及问题中必然是fast追上slow因此我们可以从距离N入手 此时两者若同时移动一次两者间的距离便会缩小1因此两者间的距离便会从N变为N - 1再变为N - 2每移动一次就会减1直到两者相遇距离变为0停止那么两者必然会相遇 距离变化如图
当fast一次走三步slow一次走一步时相遇情况 如果当fast一次走三步slow一次走一步又会发生什么呢 如图我们仍然记slow刚进环时两者间的距离为N 而当fast一次走三步slow一次走一步时两者每同时走一次两者间距离便会减少2 如图可知若N为偶数两者会相遇若N为奇数两者会错过不会相遇 那么我们可以记当N为奇数时两者间的第一次追击失败不会相遇开始第二轮追击 注意在此时我们讨论的是只有两者间的距离为0才算相遇fast一次走两步不是一步一步走而是直接跳到两步的位置 如图所示此时fast与slow的位置关系为距离-1 但是我们要讨论的是fast追击slow那么记环的周长为C的话两者间的距离就会从N变为C - 1此时开始新一轮的追击那么我们就要对C进行讨论 当C为奇数时C - 1为偶数两者间的距离每次减2可以相遇 当C为偶数时C - 1为奇数两者间的距离每次减2错过不会相遇距离还会变为-1此时又进入了新一轮的追击而距离仍然是C - 1但是与上一次追击相同C - 1仍然为奇数还是会错过不会相遇错过之后新一轮追击的距离仍然是C-1 因此当C为偶数时两者之间会进行重复的追击并且每次相差的距离都是相同的陷入了循环因此两者永远不会相遇。 当fast一次走四步slow一次走一步时相遇情况 当fast一次走四步slow一次走一步时两者间的距离会每走一次便减少三
我们继续沿用上面的图此时我们已经知道要对两者间的距离N进行讨论 而每次减少3那么就要看N是否为三的倍数情况会有三种 第一种N 3kk≥0 此时slow与fast每同时走一步距离N减少3必然会相遇 第二种N 3K 1,K≥0 此时slow与fast每同时走一步距离N减少3当两者间的距离为1时再同时走一步变为-2那么该轮追击失败进入下一轮追击 而沿顺之前的思路此时两者间的距离便会变为C - 2此时就要对C进行讨论
当C 3k时两者间的距离N1 C-2 3K-2 3(k - 1) 3 - 2 3(k - 1) 1 3k 1 注k只是一个变量相当于函数中的x替换即可因此k-1与k并无不同便于理解可将k视为x此时新一轮追击中N1每次再减少3最后距离仍变为-2即C - 2相当于进行重复操作陷入了循环因此两者不会相遇 当C 3K 1时两者间的距离N1 C - 2 3K 1 - 2 3K - 1 3K 2;
此时新一轮追击中N1每次减少3最后距离为-1即C-1不会相遇 进入新一轮追击因为C 3k1那么新距离N2 C - 1 3K 1 - 1 3K每次移动时N2减少3可以相遇 当C 3K 2时两者间的距离N1 C - 2 3K 2 - 2 3K 此时新一轮追击中N1每次减少3可以相遇 第三种N 3K 2,K≥0 我们沿顺上一种情况的思路即可。 此时slow与fast每同时走一步距离N减少3当两者间的距离为2时再同时走一步变为-1那么该轮追击失败进入下一轮追击 而沿顺之前的思路此时两者间的距离便会变为C - 1此时就要对C进行讨论 当C 3k时两者间的距离N1 C-1 3K-1 3(k - 1) 3 - 1 3(k - 1) 2 3k 2 此时新一轮追击中N1每次减少3最后距离为-1即C-1不会相遇 进入新一轮追击因为C 3k那么新距离N2 C - 1 3K - 1 3K 2相当于进行重复操作陷入了循环因此两者不会相遇 当C 3K 1时两者间的距离N1 C - 1 3K 1 - 1 3K 此时新一轮追击中N1每次减少3可以相遇 当C 3K 2时两者间的距离N1 C - 1 3K 2 - 1 3K 1 此时新一轮追击中N1每次再减少3最后距离仍变为-2即C - 2不会相遇 进入新一轮追击因此C 3K 2那么新的距离N2 C - 2 3KN2每次减少3可以相遇 总结 当fast一次走两步slow一次走一步时每同时走一次两者间的距离便会减少1因此无论N和C是偶数还是奇数两者必然会相遇 当fast一次走三步slow一次走一步时每同时走一次两者间的距离便会减少2 因此当N为偶数时可以相遇 当N为奇数时对环的周长C进行讨论当C为偶数时永远无法相遇当C为奇数时两者会相遇此时要追击两次 当fast一次走四步slow一次走一步时每同时走一次两者间的距离便会减少3 因此当N 3K时可以相遇 当N 3k 1时需要对C进行讨论当C 3k时不会相遇当C 3K 1时可以相遇此时要追击三次当C 3K 2时可以相遇此时要追击两次 当N 3K 2时需要对C进行讨论当C 3k时不会相遇当C 3K 1时可以相遇此时要追击两次当C 3K2时可以相遇此时要追击三次 如图 1.当fast一次走两步slow一次走一步时总会相遇 2.当fast一次走三步slow一次走一步时
3.当fast一次走四步slow一次走一步时
总结 本篇主要讲解了如何用O(1)的空间复杂度解决环形链表的问题同时证明了为什么可以用双指针法去解决后面会继续讲解环形链表的一个推论