2020-02-13

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

Views: 3722 | Add Comments

例如要检测如下的环, 找出 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 点. 两者相遇.

n*lam - 2*m*lam - mu + mu = n*lam - 2*m*lam

Related posts:

  1. 动态规划算法的发现
  2. 分而治之算法(divide and conquer)
  3. 史上最强大的PHP Web面试题(会做就能进百度)
  4. TCP协议思想和技术的广泛应用
  5. endless_tcp – 一种适应极端网络环境的网络软件架构
Posted by ideawu at 2020-02-13 18:12:10

Leave a Comment