|
传送门：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;//起点都是n
do{
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)
|