龟兔赛跑问题和Floyd环检测算法

栏目: IT技术 · 发布时间: 4年前

内容简介:例如要检测如下的环, 找出 a 点到 b 点的距离 mu, 以及环的周长 lam.用快慢指针同时遍历. 首先可知, 如果环存在, 快慢指针会在 c 点相遇. c 到 b 点的距离是 v. 那么可知, 相遇时, 快慢指针走过的距离是:它们是两倍关系, 所以:

例如要检测如下的环, 找出 a 点到 b 点的距离 mu, 以及环的周长 lam.

+----------------+
                |                | 
+---------------+----------------+
a    mu         b                c
                |       v        |

用快慢指针同时遍历. 首先可知, 如果环存在, 快慢指针会在 c 点相遇. c 到 b 点的距离是 v. 那么可知, 相遇时, 快慢指针走过的距离是:

慢: mu + m * lam + v
快: mu + n * lam + v

它们是两倍关系, 所以:

2 * (mu + m * lam + v) = mu + n * lam + v
2 * mu + 2 * v + 2 * m * lam = mu + n * lam + v
v = n*lam - 2*m*lam - mu

这时, 两个指针再以同样的速度前进. s 从 a 点出发, f 从 c 点出发. 可以知道, 当 s 走了 mu 距离后, 到达 b 点. 而 f 走了 mu 距离后, 也到达 b 点. 两者相遇.


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Google 广告高阶优化(第3版)

Google 广告高阶优化(第3版)

【美】Brad Geddes(布兰德.盖兹) / 宫鑫、康宁、王娜 / 电子工业出版社 / 2015-9 / 99.00元

《Google 广告高阶优化(第3版)》可以说是Google AdWords的终极指南,内容非常丰富,第三版在内容上进行了全面更新。介绍了AdWords的最新最完整的功能,阐释其工作原理,也提供了相应的优化方法、策略和实践教程,读者可以随时在自己的PPC广告系列中进行实践。第三版增添了50多页新内容,涵盖Google系统最近的所有变动,包括广告系列结构的变化、出价调整器、重定向、视频广告功能、全新......一起来看看 《Google 广告高阶优化(第3版)》 这本书的介绍吧!

html转js在线工具
html转js在线工具

html转js在线工具

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具