小编use*_*425的帖子


在乌龟和野兔算法中,为什么我们将野兔向前推进2步并进行检查

在乌龟和野兔算法中,为什么总是让兔子前进两步,然后向前前进1步,然后将它们进行比较,我们也可以使兔子前进1步,然后再次检查其是否相等,然后再增加乌龟和野兔检查它们是否相等!我认为这将有助于更快地找到循环?

例如。这个伪指令

tortoise := firstNode
hare := firstNode

forever:

  if hare == end 
    return 'No Loop Found'

  hare := hare.next

  if hare == end
    return 'No Loop Found'
   if hare==tortoise
return true

  hare = hare.next
  tortoise = tortoise.next

  if hare == tortoise
    return 'Loop Found'
Run Code Online (Sandbox Code Playgroud)

提前致谢

algorithm

1
推荐指数
1
解决办法
336
查看次数