内容简介：例如要检测如下的环, 找出 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 点. 两者相遇.
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
App研发录：架构设计、Crash分析和竞品技术分析
包建强 / 机械工业出版社 / 2015-10-21 / CNY 59.00
本书是作者多年App开发的经验总结，从App架构的角度，重点总结了Android应用开发中常见的实用技巧和疑难问题解决方法，为打造高质量App提供有价值的实践指导，迅速提升应用开发能力和解决疑难问题的能力。本书涉及的问题有：Android基础建设、网络底层框架设计、缓存、网络流量优化、制定编程规范、模块化拆分、Crash异常的捕获与分析、持续集成、代码混淆、App竞品技术分析、项目管理和团队建设等......一起来看看 《App研发录：架构设计、Crash分析和竞品技术分析》 这本书的介绍吧!
