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

郑州英语网站建设平面设计培训

郑州英语网站建设,平面设计培训,17一起做网站株洲,西安疫情最新进展前言:链表成环问题不仅考察双指针的用法,该问题还需要一定的数学推理和分析能力,看似简单的题目实则细思缜密,值得斟酌~ 目录 1.问题背景引入-判断链表是否成环: 1.1.正解:快慢指针 1.2 STL的集合判重 …

       前言:链表成环问题不仅考察双指针的用法,该问题还需要一定的数学推理和分析能力,看似简单的题目实则细思缜密,值得斟酌~

目录

1.问题背景引入-判断链表是否成环:

1.1.正解:快慢指针

1.2 STL的集合判重

2.判断入环点问题

2.1.正解:快慢指针

思路分析

代码实现

2.2.相遇点断开判断相交点

思路分析

代码实现

3.金句频道


1.问题背景引入-判断链表是否成环:

1.1.正解:快慢指针

对于这个经典问题,一般的,我们得最优解法就是使用快慢指针,下面我们先来分析一下原理:

 

1.2 STL的集合判重

STL还是很好用的,只是会在时间和空间上比双指针算法性能差一些,但胜在思路简单清晰

class Solution {
public:bool hasCycle(ListNode *head) {//快慢指针/*ListNode *slow=head;ListNode *fast=head;bool result=false;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;if(slow==fast){result=true;break;}}return result;*///C++ STL的setset<ListNode *>mp;ListNode *p=head;while(p){if(!mp.count(p)){mp.insert(p);p=p->next;}elsereturn true;}return false;}
};

2.判断入环点问题

       如果我们需要判断是否成环并在成环前提下找出环的入口节点呢,诸位有什么好方法吗?可以先停下来思考片刻,

 这个题看起来容易,实际上需要用数学归纳法推出可行性的结论进行处理,我们来看。

2.1.正解:快慢指针

思路分析

我们还是用上面所讲的双指针算法,我们这里先给出结论:

  一个指针从相遇点开始走,一个指针从链表头开始走,它们会在环的入口点相遇.

下面我们来做一下推导证明: 

我们来假设下列条件:

根据上图所示,我们来看fast和slow分别走了多少步?

       首先,我们需要知道,fast和slow指针的相遇,会在slow在环内部转了几圈后再追上吗?

这个显然是不可能的,其原因,就是当slow开始进入环时,fast已经在环中的某个点上,此后slow每走一步,fast都会走slow所到节点的两倍,现在变成了fast从slow的背后追slow,并且,slow每走一步,fast都会从它背后追赶两步,造成了两者之间的距离每次缩小1,由于fast在开始追slow是就已经在环中了,所以不用一个环的长度,fast必然追上slow。

        这样一来就好算了,slow走的距离就是L+x,而fast走的距离就是L+C+x,我们可以根据2*slow=fast列出等量关系

                                            2(L+x)=L+C+x;

可以解得:L=C-x,

我知道你急,但是先别急~

如果我的链表是C=1,L=3呢?3=1-(-2)吗?很显然,这不符合逻辑,这是因为我们忽视了一个问题:当L>>C的时候,fast会在环中转很多次才能等到slow进入环中,我们假设这种情况下fast在slow进入环中之前已经转了n次,那么我们的fast走过的实际距离应该为

                                          fast=L+n*C+x;

     此时我们的等式变为:2*(L+x)=L+n*C+x

可以解得

                                        

                                               L=n*C-x;

我们将上面的结论反馈到图中

 进而,我们就可以得出结论,

一个指针从相遇点开始走,一个指针从链表头开始走,它们会在环的入口点相遇.

代码实现

class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode *slow=head;ListNode *fast=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;if(slow==fast){ListNode *meet=slow;//相遇节点//相遇节点和头结点同时走,相遇到的点就是入环节点while(head!=meet){head=head->next;meet=meet->next;}return head;}}return NULL;}
};

2.2.相遇点断开判断相交点

思路分析

       这个思路不难理解,只要我们将相遇点的下一个节点置为NULL,记住相遇点的下一个节点,然后和头结点一起遍历找出地址相同的节点即为入环节点:

代码实现

class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode *slow=head;ListNode *fast=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;if(slow==fast){//相遇节点//cout<<slow->val<<endl;//cout<<fast->val<<endl;ListNode *meetnext=slow->next; //cout<<meetnext->val<<endl;slow->next=NULL;//断开链表,然后开始找两个链表的相交节点//这里我为了方便,直接用STL来判重,写个链表求长度函数,然后将长的链表遍历到和短链表长度一致时再同时开始遍历也可以set<ListNode*> mp;ListNode *p1=head;ListNode *p2=meetnext;//步骤还可以优化while(p1||p2){if(p1&&!mp.count(p1)){mp.insert(p1);p1=p1->next;}else if(p1&&mp.count(p1))return p1;if(p2&&!mp.count(p2)){mp.insert(p2);p2=p2->next;}else if(p2&&mp.count(p2))return p2;}  }}return NULL;}
};

3.金句频道

想什么呢,向前走啊你

      你可以消沉,也可以抱怨,但希望天一亮,你又能顶住四面八方的压力,继续努力的好好生活。不要总抓着过去的事情不放,对那些受过的委屈和伤害耿耿于怀,以及在那些根本无法改变的人和事上面无谓的消耗自己,我们人生的进步就是我们的能力和我们的梦想一次次匹配。

 

http://www.khdw.cn/news/35102.html

相关文章:

  • 17网站一起做网店 新塘seo合作
  • 有什么做户外活动的网站吗新闻软文范例大全
  • 山东省和住房建设厅网站公司企业网站制作需要多少钱
  • 做网站应该学什么专业进行seo网站建设
  • 网站限制复制企业网页设计报价
  • 个人网页制作与网站建设怎么做自己的网站
  • 镇江网站建设活动方案seo关键词排名优化专业公司
  • 做简单的网站多少钱海外短视频跨境电商平台是真的吗
  • 建设隔热网站网站查询域名ip
  • canvas网站源码5118数据分析平台
  • 重庆大渡口营销型网站建设公司哪家好百度关键词怎么做
  • 报价网站系统seo关键词排名优化品牌
  • 顺义做网站公司百度官方网站入口
  • 内蒙古网络公司有哪些网站seo排名优化工具
  • 衡水提供网站制作公司哪家好网站推广网络营销
  • 网站建设主要流程图网站开发与设计
  • 茂南网站建设公司手机360优化大师官网
  • js做网站好吗百度快照优化排名怎么做
  • 淮安市住房和城乡建设局网站优化设计数学
  • 建工行业建设标准网站个人网站制作模板主页
  • 昆明门户网站淘宝付费推广有几种方式
  • 搜狗推广做网站要钱吗营销型网站建设排名
  • 网站建设资料准备各引擎收录查询
  • 做弹弓教程网站广州seo报价
  • 建立网站备案需要什么资料快手作品免费推广软件
  • 温州手机网站制作联系电话目前推广平台都有哪些
  • 电子外贸网站模板怎么找一手app推广代理
  • 网站的着陆页seo排名助手
  • 网站红色模板恶意点击软件有哪些
  • 外贸网站制作策划杭州seo论坛