Этот блог помогает понять, как использовать алгоритм черепахи и зайца (алгоритм Флойда) для решения различных технических проблем. Этот алгоритм назван в честь Роберта У. Флойда. Основное использование этого алгоритма - для задач, прямо или косвенно связанных с обнаружением цикла. Итак, начнем с первой проблемы:

Leetcode 141: для заданного head, заголовка связанного списка, определить, есть ли в связанном списке цикл.

Прочитав описание вышеупомянутой проблемы Leetcode, мы можем сделать вывод, что нам нужно проверить наличие кругового связанного списка. Нам нужно будет использовать два указателя (медленный и быстрый), которые будут вести себя как черепаха и заяц. Если связанный список является круговым, он будет иметь два типа узлов: те, которые находятся за пределами цикла, и другие внутри цикла. Мы заставим медленный указатель перескочить на один узел, в то время как быстрый указатель переместится на два узла. Как только медленные и быстрые указатели указывают на узлы внутри цикла, они будут продолжать двигаться по кругу, пока не встретятся. Но, если связанный список не круговой, указатели достигнут нулевого (последнего) узла. Решение в JAVA будет выглядеть примерно так:

public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null){
            return false;
        }
        ListNode slow = head;  //Initializing tortoise and hare
        ListNode fast = head;
        while(fast.next!=null&&fast.next.next!=null){
            slow = slow.next;
            fast = fast.next.next;//Hare is faster than Tortoise
            if(slow==fast){
                return true;// if they meet then cycle is present
            }
        }
        return false; // if pointers reach at null then no cycle
        
    }
}

После этого вопроса вы можете самостоятельно задать дополнительный вопрос, Linked List Cycle II. Теперь давайте применим этот алгоритм к проблеме, которая не связана со связанным списком:

Leetcode 287: Найдите повторяющийся номер.

Дан массив nums целых чисел, содержащий n + 1 целых чисел, где каждое целое число находится в диапазоне [1, n] включительно. В nums есть только одно повторяющееся число, верните это повторяющееся число.

Постановка задачи не дает намеков на алгоритм, необходимый для ее решения. Но диапазон [1, n] чисел помогает указать, что мы можем использовать значения массива в качестве индекса. Предыдущая подсказка может сначала не «щелкнуть», но если вы решите несколько таких проблем с помощью Leetcode, вы сможете ее получить.

Правильный метод использования алгоритма Флойда аналогичен исходному алгоритму, то есть путем инициализации медленных и быстрых указателей. Здесь метод создания медленного указателя заключается в том, чтобы заставить его перейти к следующему узлу индекса, равного текущему значению (поскольку 1≤index≤n), а для быстрого указателя переход выполняется дважды. После обхода массива два указателя пересекутся в значении, и эта точка поможет нам найти окончательное повторяющееся значение.

На приведенном выше рисунке показаны три значения - F, a, C-a. Расстояние, пройденное черепахой (медленный указатель), будет F + a, а расстояние, пройденное Зайцем, будет F + a + xC, где x обозначает количество циклов. А поскольку один из них прошел вдвое большее расстояние, следовательно, F + a = xC. Мы поместим Hare в начало (индекс 0) и поставим оба указателя с одинаковой скоростью. Причина этого в том, что Черепаха должна пройти C-расстояние, чтобы достичь общего значения, а Заяц должен пройти F. Следовательно, обе позиции одинаковы.

Код для вышеупомянутой проблемы будет:

class Solution {
    public int findDuplicate(int[] nums) {
        if (nums.length > 1){
            int slow = nums[0];
            int fast = nums[nums[0]];
            
            while (slow != fast){
                //making Hare twice as fast as Tortoise
                slow = nums[slow];
                fast = nums[nums[fast]];
                
            }
            //Hare is sent back to starting
            fast = 0;
            
            while (fast != slow){
                //Both move at same speed
                fast = nums[fast];
                slow = nums[slow];
                
            }
            return slow; // Final Destination!!
     }
     return -1;   
    }
}

Спасибо за чтение и удачного кодирования !!!!!!!