本文主要是介绍Floyed 判圈算法/龟兔赛跑法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门：http://blog.csdn.net/thestoryofsnow/article/details/6822576
作用：检测一个链表是否有环，如果有环，求出环的起点
int *head=list.GetHead();//链表起点
if(head!=null){//起初，快的和慢的都在链表起点 int *fast=head;int *slow=head;bool isCircular=true;//做标记 do{//如果还没相遇 快的就已经到达尽头，表明无环 if(fast->Next==null||fast->Next->Next==null){isCircular=false;break;}fast=fast->Next->Next;//快的一次走两步 slow=slow->Next;//慢的一次走一步 }while(slow!=fast);//有环 slow=head;//将慢的移到链表起点 while(fast!=slow){slow=slow->Next;//让快的和慢的以相同的步伐前进 fast=fast->Next;}//最后相遇的点就是环的起点 cout<<"the starting point of the cycle is "<<slow<<endl;
}例题：
LeetCode202. 快乐数
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为：
- 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
- 如果 可以变为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 true ；不是，则返回 false 。
示例 1：
输入：19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
思路：由题意得：无限循环时变不到1，即不是快乐数。那么等价于看有没有环，如果形成了环，且环得一个起点是1，它就是快乐数。
所以是龟兔赛跑法。
代码如下：
#include <bits/stdc++.h>
using namespace std;
int n;
int digitSquareSum(int n){//获取这个数每个位置上的数字的平方和int sum=0,temp;while(n){temp=n%10;sum+=temp*temp;n/=10;}return sum;
}
bool isHappy(int n){int slow,fast;slow=fast=n;//起点都是ndo{slow=digitSquareSum(slow);//慢的跑一步fast=digitSquareSum(fast);//快的跑两步fast=digitSquareSum(fast);}while(slow!=fast);if(slow==1) return 1;//如果是1，满足条件else return 0;
}
int main(){cin>>n;if(isHappy(n)) puts("YES");else puts("NO");return 0;
}以它为基础的Pollard's Rho算法：质因数分解算法，复杂度：O(1)
这篇关于Floyed 判圈算法/龟兔赛跑法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
