Floyd判圈算法
leetcode 上 编号为202 的happy number 问题，有点意思。happy number 的定义为：
A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.
如 19 就是一个 happy number :
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
12就不是一个happy number :
1^2 + 2^2 =5
5^2 = 25
2^2 + 5^2 = 29
2^2 + 9^2 = 85
8^2 + 5^2 = 89 <—-
8^2 + 9^2 = 145
1^2 + 4^2+ 5^2 = 42
4^2 + 2^2 = 20
2^2 + 0^2 = 4
4^2 = 16
1^2 + 6^2 = 37
3^2 + 7^2 = 58
5^2 + 8^2 = 89 <—-
… …
可以发现如果一个数是一个 happy number，那么最终是1循环，比较容易判断。如果一个数不是 happy number，那么存在一个循环，其中不包含1，这就比较难判断，因为不清楚这个循环周期大小。一种解决思路是通过 HashSet 来存取数字，如果这个数字之前存储好了，说明进入一个循环。代码如下：
public class Solution {
public boolean isHappy(int n) {
HashSet<Integer> set = new HashSet<Integer>();
while(!set.contains(n)) {
set.add(n);
n = getSquSum(n);
if(n == 1) {
return true;
}
}
return false;
}
public int getSquSum(int n) {
int sum = 0;
int t;
while(n != 0){
t = n % 10;
sum += t * t;
n = n / 10;
}
return sum;
}
}
有种比较巧妙的思路是：Floyd判圈算法。wikipedia 上的说明是：
Floyd判圈算法(Floyd Cycle Detection Algorithm)，又称龟兔赛跑算法(Tortoise and Hare Algorithm)。该算法由美国科学家罗伯特·弗洛伊德发明，是一个可以在有限状态机、迭代函数或者链表上判断是否存在环，求出该环的起点与长度的算法。
初始状态下，假设已知某个起点节点为节点S。现设两个指针t和h，将它们均指向S。接着，同时让t和h往前推进，但是二者的速度不同：t每前进1步，h前进2步。只要二者都可以前进而且没有相遇，就如此保持二者的推进。当h无法前进，即到达某个没有后继的节点时，就可以确定从S出发不会遇到环。反之当t与h再次相遇时，就可以确定从S出发一定会进入某个环。
class Solution {
public:
bool isHappy(int n) {
int slow = n;
int fast = sqrtSum(n);
while(fast != 1 && slow != fast) {
fast = sqrtSum(fast);
if(fast != 1 && slow != fast) {
fast = sqrtSum(fast);
slow = sqrtSum(slow);
}
}
return fast == 1;
}
int sqrtSum(int n) {
int sum = 0;
while(n) {
sum += (n % 10) * (n % 10);
n = n / 10;
}
return sum;
}
}
