# Floyd Cycle Detection Algorithm的应用

## September 20, 2016

https://leetcode.com/problems/find-the-duplicate-number/



# Floyd Cycle Detection Algorithm

Python代码如下(via Wikipedia):

def brent(f, x0):
# main phase: search successive powers of two
power = lam = 1
tortoise = x0
hare = f(x0)  # f(x0) is the element/node next to x0.
while tortoise != hare:
if power == lam:  # time to start a new power of two?
tortoise = hare
power *= 2
lam = 0
hare = f(hare)
lam += 1

# Find the position of the first repetition of length λ
mu = 0
tortoise = hare = x0
for i in range(lam):
# range(lam) produces a list with the values 0, 1, ... , lam-1
hare = f(hare)
# The distance between the hare and tortoise is now λ.

# Next, the hare and tortoise move at same speed until they agree
while tortoise != hare:
tortoise = f(tortoise)
hare = f(hare)
mu += 1

return lam, mu


Given a linked list, determine if it has a cycle in it.

Can you solve it without using extra space?

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
return false;
while(pmove&&qmove&&qmove->next){
pmove=pmove->next;
qmove=qmove->next->next;
if(pmove==qmove)
return true;
}
return false;
}
};


# 142. Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Can you solve it without using extra space?

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
return NULL;
while(fast&&fast->next){
fast=fast->next->next;
slow=slow->next;
if(fast==slow){
while(entry!=slow){
entry=entry->next;
slow=slow->next;
}
return entry;
}
}
return NULL;
}
};


# 287. Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Note:

1.You must not modify the array (assume the array is read only).

2.You must use only constant, O(1) extra space.

3.Your runtime complexity should be less than O(n2).

4.There is only one duplicate number in the array, but it could be repeated more than once.

class Solution {
public:
int findDuplicate(vector<int>& nums) {
if(nums.empty())
return 0;
int slow=nums[0],fast=nums[nums[0]];
while(slow!=fast){
slow=nums[slow];
fast=nums[nums[fast]];
}
fast=0;
while(fast!=slow){
slow=nums[slow];
fast=nums[fast];
}
return fast;
}
};



### 学籍管理系统文档

#### 北邮教务系统评教脚本

Published on September 17, 2017

#### 72.Edit distance

Published on September 17, 2017