Java教程

Floyd 判圈算法

本文主要是介绍Floyd 判圈算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

目录
  • 以下是引用 wiki 的介绍:
  • 个人的理解:
  • 1、演示
    • 下面进行演示。假设头节点为0,第六号节点的子节点为第2号节点,所以有 2->3->4->5->6->3 成环。设 t 与 h 在环内相遇于 A 点
  • 2、求环内交点
  • 3、求环入口
  • 4、求环长度
  • 5、代码汇总

Floyd判圈算法

以下是引用 wiki 的介绍:

Floyd判圈算法(Floyd Cycle Detection Algorithm),又稱龜兔賽跑算法(Tortoise and Hare Algorithm),是一個可以在有限狀態機、迭代函數或者鍊表上判斷是否存在環,求出該環的起點與長度的算法。

​ 如果有限狀態機、迭代函數或者鍊表存在環,那麼一定存在一個起點可以到達某個環的某處(這個起點也可以在某個環上)。

初始狀態下,假設已知某個起點節點為節點S。現設兩個指針t和h,將它們均指向S。

​ 接著,同時讓t和h往前推進,但是二者的速度不同:t每前進1步,h前進2步。只要二者都可以前進而且沒有相遇,就如此保持二者的推進。當h無法前進,即到達某個沒有後繼的節點時,就可以確定從S出發不會遇到環。反之當t與h再次相遇時,就可以確定從S出發一定會進入某個環,設其為環C。

​ 如果確定了存在某個環,就可以求此環的起點與長度。

​ 上述算法剛判斷出存在環C時,顯然t和h位於同一節點,設其為節點M。顯然,僅需令h不動,而t不斷推進,最終又會返回節點M,統計這一次t推進的步數,顯然這就是環C的長度。

​ 為了求出環C的起點,只要令h仍均位於節點M,而令t返回起點節點S,此時h與t之間距為環C長度的整數倍。隨後,同時讓t和h往前推進,且保持二者的速度相同:t每前進1步,h前進1步。持續該過程直至t與h再一次相遇,設此次相遇時位於同一節點P,則節點P即為從節點S出發所到達的環C的第一個節點,即環C的一個起點。


个人的理解:

​ 开始时,t与h都位于头节点,每次h先移动2单位,之后判断h是否与t在同一点内,若不在,则轮到t移动一单位;若在同一点,则说明存在一个环。否则如此往复,h一定会移动到链表的尾端,即无法再移动,这种情况便是不存在环的情况。

1、演示

下面进行演示。假设头节点为0,第六号节点的子节点为第2号节点,所以有 2->3->4->5->6->3 成环。设 t 与 h 在环内相遇于 A 点

image-20211010115731156

image-20211010115755658

image-20211010115807266

image-20211010115830671

image-20211010120056350

至于为什么有环会相遇,这点很好理解。想象两个不同速度的人在操场上跑步。即使慢的人领先与快的人,到最后快的人也会追上慢的人。

2、求环内交点

现在来说明一下,为什么如果有环的话,为什么快指针会在一圈之内追上慢指针。

image-20211010121348374

已知 t(慢指针) 的速度为 1/s
	h(快指针) 的速度为 2/s

假设在 t 刚入环时,h 在环内的位置距离入环点的距离为 b,设 环长度为 L。
则此时 h 与 t之间的距离(追赶距离)为 L - b
而 h 与 t 的相对速度为:(2-1)/s,也就是每一个周期,h与t的距离都会缩短一个单位
所以,当 h 与 t 相遇时,他们所想好的时间为:(L-b)/(2-1) = (L-b)/s
由于t的速度为1/s 所以,t 与 h 相遇时,t所走的距离为(L-b)
上式中,仅当 b=0 时 t 需要走一圈之后才能与h相遇,但 b=0 这条件是不存在的
	若 b=0 这存在,这说明,t刚好追赶上h时是在入环口。
	但这很明显是不可能的,起始时h先手走两单位,之后才到t移动一单位。因此在不存在环的情况下,
	t 永远追及不到 h(这也是判断是否有环的思路)
所以,L-b 一定小于 L 即h在环内可以在一圈之内追及上t
/**
     *求环内交点
     * @param head 头节点
     * @return 如果存在环,则返回环内快慢指针相交的节点;若无则返回null
     */
public static ListNode FindIntersection(ListNode head) {
    ListNode h = head, t = head;
    while (h != null ) {
        if (h.next != null) {
            h = h.next;
            t = t.next;
        }
        else {
            return null;
        }
        if (h.next != null) {
            h = h.next;
            //每次h跑完两步就要检查一下是否追上了t,这里可能会有人有疑问,为什么上面h刚跑完之后不检查是否追上了t
            //这是因为,后面需要根据这个点来求入环点,而推导公式的基础便是每次h行动2单位都是不可分割的。
            if (t == h) {
                return t;
            }
        }
    }
    return null;
}

3、求环入口

image-20211010191638433

如上图,设环外长度为a,h与t相交于环内的A点,其距离入环口的距离为b,一圈长度为 C

​ 由上面的现在来说明一下,为什么如果有环的话,为什么快指针会在一圈之内追上慢指针。可知,相遇时,t在环内走过的距离不会超过一圈

  • 则 t移动的距离为:Lt = a + C*0 + b
  • 则 h移动的距离为:Lh = a + C*n + b
  • 由于h移动的总距离为t的两倍,则有 Lh-Lt = Lt = (a + C*0 +b ) - (a + C*n + b) = C*n

所以可见 Lt 为环长的整数倍。

现在让 t 指针回到头节点,h 指针保持在 A 点,然后 两指针同步的一起移动 a 单位(其中t指针的作用是贡献 a 长度,使其与环内的已有长度 b 的 h 构成刚好一个环的长度)到达环入口。由于一开始 h 在环内距离入环点的距离为 b ,所以当 t 移动了 a 单位时,h在环内的长度为 b + a = Lt 所以此时 h 也刚好到达环入口(想一下,从一个地方进入操场跑一圈当然是会回到入口点的)。

所以当 t 与 h相交时便是环的入口。

public ListNode detectCycle(ListNode head) {
    if (head == null) {
        return null;
    }
    ListNode intersListNode = FindIntersection(head);
    if (intersListNode != null) {
        while (head != intersListNode) {
            head = head.next;
            intersListNode = intersListNode.next;
        }
        return head;
    } else {
        return null;
    }
}

4、求环长度

当找到环内交点时,令其中指针一个不动,而另一个指针每次移动一单位。最后再次相遇时所走过的距离便是环的长度。

/**
 *
 * @param intersListNode 循环圈内 快慢指针的交点
 * @return 一个圈的长度
 */
public static int LoopLength(ListNode head ,ListNode intersListNode) {
    int cnt = 0;
    //无环的情况
    if (intersListNode == null)
        return cnt;
    //无环外长的情况
    if (head == intersListNode) {
        cnt++;
        head = head.next;
        while (head != intersListNode && cnt++>0)
            head = head.next;

    }
    //有环外长的情况
    else {
        ListNode t = intersListNode.next;
        cnt++;
        while (t != intersListNode && cnt++>0)
            t = t.next;
    }
    return cnt;
}

5、代码汇总

import java.util.ArrayList;
import java.util.HashMap;

// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }

}

public class Solution {

    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode intersListNode = FindIntersection(head);
        if (intersListNode != null) {
            while (head != intersListNode) {
                head = head.next;
                intersListNode = intersListNode.next;
            }
            return head;
        } else {
            return null;
        }
    }

    /**
     *
     * @param head 头节点
     * @return 如果存在环,则返回环内快慢指针相交的节点;若无则返回null
     */
    public static ListNode FindIntersection(ListNode head) {
        ListNode h = head, t = head;
        while (h != null ) {
            if (h.next != null) {
                h = h.next;
                t = t.next;
            }
            else {
                return null;
            }
            if (h.next != null) {
                h = h.next;
                //每次h跑完两步就要检查一下是否追上了t,这里可能会有人有疑问,为什么上面h刚跑完之后不检查是否追上了t
                //这是因为,后面需要根据这个点来求入环点,而推导公式的基础便是每次h行动2单位都是不可分割的。
                if (t == h) {
                    return t;
                }
            }
        }
        return null;
    }

    /**
     *
     * @param intersListNode 循环圈内 快慢指针的交点
     * @return 一个圈的长度
     */
    public static int LoopLength(ListNode head ,ListNode intersListNode) {
        int cnt = 0;
        //无环的情况
        if (intersListNode == null)
            return cnt;
        //无环外长的情况
        if (head == intersListNode) {
            cnt++;
            head = head.next;
            while (head != intersListNode && cnt++>0)
                head = head.next;

        }
        //有环外长的情况
        else {
            ListNode t = intersListNode.next;
            cnt++;
            while (t != intersListNode && cnt++>0)
                t = t.next;
        }
        return cnt;
    }

    /**
     *
     * @param enm 链表的前后驱节点的关系
     * @param head 头节点
     * @return 尾结点
     */
    public static ListNode init(int[][] enm, ListNode head) {
        HashMap<Integer, ListNode> map = new HashMap<Integer, ListNode>();
        ListNode t = head;
        map.put(0, head);
        for (int i = 0; i < enm.length; i++) {
            ListNode node;
            if (map.containsKey(enm[i][1])) {
                node = map.get(enm[i][1]);
            }
            else {
                node = new ListNode(enm[i][1]);
                map.put(enm[i][1], node);
            }
            t.next = node;
            t = node;
        }
        return t;
    }

    public static void main(String[] st) {
        ListNode head = new ListNode(0);
        Solution ss = new Solution();
        // int[][] enm = { { 0, 1 }, { 1, 2 }, { 2, 3 }, { 3, 4 }, { 4, 5 }, { 5, 6 }, { 6, 3 } };
        int[][] enm = { { 0, 1 }, { 1, 0}};
        init(enm, head);
        System.out.println(LoopLength(head, FindIntersection(head)));
        System.out.println(ss.detectCycle(head).val);
    }
}

这篇关于Floyd 判圈算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!