Этот блог помогает понять, как использовать алгоритм черепахи и зайца (алгоритм Флойда) для решения различных технических проблем. Этот алгоритм назван в честь Роберта У. Флойда. Основное использование этого алгоритма - для задач, прямо или косвенно связанных с обнаружением цикла. Итак, начнем с первой проблемы:
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; } }
Спасибо за чтение и удачного кодирования !!!!!!!