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

怎么做网站 教学重庆seo是什么

怎么做网站 教学,重庆seo是什么,徐州方案公示在哪个网站,企业宣传册怎么制作💓 博客主页:倔强的石头的CSDN主页 📝Gitee主页:倔强的石头的gitee主页 ⏩ 文章专栏:《数据结构与算法 经典例题》C语言 期待您的关注 ​ 目录 一、问题描述 二、解题思路 方法一:数学公式推导法 方法…

             💓 博客主页:倔强的石头的CSDN主页 

             📝Gitee主页:倔强的石头的gitee主页

   ⏩ 文章专栏:《数据结构与算法 经典例题》C语言

                                  期待您的关注

1b7335aca73b41609b7f05d1d366f476.gif

目录

一、问题描述

二、解题思路

方法一:数学公式推导法

方法二:转换为相交链表问题求解

三、代码实现

方法一实现代码

方法二实现代码


一、问题描述

原题链接   142. 环形链表 II - 力扣(Le142. 环形链表 II - 力扣(Le

二、解题思路

方法一:数学公式推导法

预备知识

此方法的数学推导建立在判断链表是否带环的基础算法上,推荐阅读前置文章

点击下方文字

【数据结构与算法 刷题系列】判断链表是否有环-CSDN博客

 如图,通过快慢指针法得到两个指针相遇位置时

假设:

  • 链表入环前的长度为L
  • 环的长度为C
  • 快慢指针相遇节点为meet
  • 环的入口与相遇节点meet的距离为N
  • 相遇时,快指针已经在环内走了X圈(X>=1,快指针至少比慢指针都走一圈才能追上)
推导过程:

在meet相遇点

慢指针移动距离为L+N

快指针移动距离为L+X*C+N

 

另外,快指针移动距离是快指针的两倍

快指针也可以写成2(L+N)

将两条公式结合起来

2(L+N)=L+X*C+N

化简

L+N=X*C

L=X*C-N

L=(X-1)*C+C-N    

 最终得到的公式:

L=(X-1)*C+C-N    

该公式在图中说明的问题:

链表入环前的长度L

与相遇点到环入口的距离再加(X-1)圈      ——X最少为1,所以X-1至少为0

是相等的

结论:

如果两个指针分别从链表起始位置和相遇点meet开始移动,那么两个指针第一次相遇的节点就是环的入口

方法二:转换为相交链表问题求解

此方法的数学推到建立在判断链表是否带环的基础算法上,推荐阅读

【数据结构与算法 刷题系列】相交链表-CSDN博客

该方法是将带环链表问题转换为相交链表问题,将问题降级处理

 首先,依然要 求得快慢指针相遇交点

然后将取得该节点下一个节点地址,令其成为一个单独链表的首节点,断开链表 

 之后,这个问题就可以转换为相交链表问题来解决

 

三、代码实现

方法一实现代码

struct ListNode {int val;struct ListNode* next;};
typedef struct ListNode ListNode;//方法一:数学推理法
struct ListNode* detectCycle1(struct ListNode* head)
{ListNode* slow, * fast;slow = fast = head;ListNode* meet = NULL;while (fast && fast->next){slow = slow->next;fast = fast->next->next;if (slow == fast)//先求得快慢指针相遇节点{meet = slow;while (meet != head)//两指针同时移动,相遇即是入口{meet = meet->next;head = head->next;}return meet;}}return NULL;
}

方法二实现代码

//求相交链表的交点的函数
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{ListNode* pcurA = headA;ListNode* pcurB = headB;int countA = 0;int countB = 0;while (pcurA)//求出链表长度{pcurA = pcurA->next;countA++;}while (pcurB){pcurB = pcurB->next;countB++;}int tmp = abs(countA - countB);//长度差值ListNode* slow, * fast;if (countA < countB){slow = headA;fast = headB;}else{slow = headB;fast = headA;}while (tmp--)//长链表先走差值的步数{fast = fast->next;}while (fast && slow)//同步比较{if (fast == slow)return fast;fast = fast->next;slow = slow->next;}return NULL;
}
struct ListNode* detectCycle(struct ListNode* head)
{ListNode* slow, * fast;slow = fast = head;ListNode* meet = NULL;while (fast && fast->next){slow = slow->next;fast = fast->next->next;if (slow == fast)//先求得快慢指针相遇节点{meet = slow;ListNode* newhead = meet->next;meet->next = NULL;//将环断开,变成两个相交的链表return getIntersectionNode(head, newhead);}}return NULL;
}

总结

两种方法可以自行选用
第一种方法属于推理复杂,代码简单

第二种方法属于推理简单,代码实现细节复杂

可根据实际情况选择合适的方法

http://www.dinnco.com/news/64239.html

相关文章:

  • 阿里云网站域名备案百度指数官网
  • 怎么做云购网站免费seo快速排名系统
  • 企业网站建站元素短视频代运营公司
  • 福州市疫情最新情况百度谷歌seo优化
  • 宁波建站模板企业网站建设方案模板
  • 网站建设实验后体会企业管理咨询培训
  • 东莞视频课程网站建设百度推广登录后台
  • 婚介网站建设google play下载
  • 公司没有自己的网站seo是什么意思职业
  • 重庆工程建设信息网证件查询优化网站服务
  • 怎么做质量高的网站西安网站建设网络推广
  • 云南网站建设招商信息流投放平台
  • 苏宁易购电子商务网站建设目标厨师培训学校
  • 仿《爱美眉》网站 dede包头整站优化
  • 怎么做免费网站被收录今日实时热点新闻事件
  • 天津做网站的哪家好微信小程序平台官网
  • 国内网站模板seo是什么车
  • wordpress站群seo如何推广网站方法
  • 连云港权威网站建设价格今日头条十大新闻最新
  • 网站子目录快速排名优化系统
  • 项目申报东莞搜索优化十年乐云seo
  • 苏州网站建设书生新闻联播俄罗斯与乌克兰
  • 虎门做网站2022年可以打开的网址
  • 学做网站要编程百度客服怎么转人工电话
  • 虎门网站建设服务商如何创建一个网页
  • 自己做网站需不需要钱关键词排名优化报价
  • 当当网网站建设做网络推广为什么会被抓
  • 找哪个公司做网站推广最好搜索引擎优化的核心是
  • 网站开发ppt转h5深圳百度推广seo公司
  • 有哪些好用的网站seo优化网站网页教学