close
通常用來detect loop，判斷從哪段開始有loop
解法可以想像是龜兔賽跑，兔子兩倍速，烏龜一倍速前進
假設c是起點距離loop的距離，k是起點距離第一次相遇點的距離，loop 長度是L
第一次相遇的k點，會正好是L-c，
所以如果相遇後兔子回到原點，烏龜留在k點，都用一倍速前進，會正好二次相遇在loop起始點，因此可以得到 c
之後兔子不動，烏龜在一倍速移動，第三次相遇時可得到 L
這邊的最重要的想法在第一次相遇時為什麼正好會在 L-c，有重要想法
當烏龜進入loop時，兔子正好也超前c的距離，但這也意味著兔子在loop裡有 L-c 的距離要追烏龜
今天如果是都一倍速，那麼L-c的距離就會一直維持，
但是今天兔子每次都快烏龜一步，所以當龜兔相遇時，就會正好在 loop 在L-c的位子
大概就是這樣，其實這個解法我之前碰過一次，但是可能沒想懂，第二次來還是想的卡卡的，所以在這邊寫下來
全站熱搜
留言列表
leetcode (3)
