我理解Floyd的循环检测算法的概念.它的结论是,如果乌龟的行进速度是野兔的两倍,如果乌龟在一个循环中有一个k米的起点,那么乌龟和野兔将在循环之前达到k米.
在单链表的情况下,你的指针A的行进速度是指针B的两倍.这意味着如果它需要指针B k步到达循环的入口点(我们还不知道它在哪里),指针A将在循环内已经有k个节点的开头.因此,两个指针将在循环的入口点之前与k个节点相遇.因此,如果我们将指针B移回头指针并将指针A保持在会合点(现在两个指针都是远离入口点的k个节点),并以相同的速度移动它们,它们将在入口点处相遇循环.
如何证明该算法适用于以下边界情况？
这不是功课.面试官告诉我,如果我有一个小循环,这个算法将不起作用.他没有解释原因.
考虑以下链接列表：
1->2->3->4->5->6->7->8->9->4->...->9->4.....
上面的列表有一个循环，如下所示：
[4->5->6->7->8->9->4]
在白板上绘制链接列表，我尝试手动解决不同的指针步骤，以查看指针如何移动 -
(slow_pointer_increment, fast_pointer_increment)
因此，针对不同情况的指针如下：
(1,2), (2,3), (1,3)
前两对增量 - (1,2) 和 (2,3) 工作得很好，但是当我使用 (1,3) 对时，该算法似乎不适用于该对。是否有一个规则规定我们需要增加多少步数才能使该算法成立？
尽管我搜索了较慢和较快指针的各种增量步骤，但到目前为止，我还没有找到一个相关答案来解释为什么它不适用于此列表中的增量 (1,3)。
通过哈希，我有一个“工作”列表，每个工作都有一个 id 和一个 Parent。具有父级的作业只有在其父级执行完毕后才能执行。我如何检测依赖循环？
数据集如下图所示：
jobs = [
{:id => 1, :title => "a", :pid => nil},
{:id => 2, :title => "b", :pid => 3},
{:id => 3, :title => "c", :pid => 6},
{:id => 4, :title => "d", :pid => 1},
{:id => 5, :title => "e", :pid => nil},
{:id => 6, :title => "f", :pid => 2},
]
'id' 的顺序是： 1 > 2 > 3 > 6 > 2 > 3 > 6.... 等等
说我有一个函数f:
f(0) = 0
f(i) = (i - 1) % 4
F(0..12):
0 0 1 2 3 0 1 2 3 0 1 2 3
我想找到循环开始和循环长度,分别为1和4.乌龟和野兔算法适用于迭代函数,但我没有迭代函数.是否有其他算法可以使用非迭代函数,或者可以为此修改龟和野兔算法？
编辑:
使用Jason S的答案,我设法提出了这个,这似乎是有效的:
public static Tuple<int, int> ModifiedTortoiseHare(Func<int, int> f, int x0 = 0, int checks = 4)
{
for (; ; x0++)
{
int lam = 0, tortoise, hare;
do
{
lam++;
tortoise = f(x0 + lam);
hare = f(x0 + 2 * lam);
} while (tortoise != hare);
int mu = -1; …在访谈问题中,"实现一种检测循环存在的算法".例如,链表有一个循环,如:
0--->1---->2---->3---->4---->5---->6
? |
| ?
11<—-22<—-12<—-9<—-8
使用Floyd的循环检测,可以通过使用快速和慢速指针来解决此问题.我应该尝试比较
一个.链接的节点值,即
if (fast.data == slow.data)
break;
快速和慢速的类型 Link
class Link
{
int IData {get; set;}
Link Next {get; set;}
}
要么
湾 他们是否指向相同的参考,即if (fast == slow)
谢谢.