Floyd判圈算法

---

leetcode 上 编号为202 的happy number 问题，有点意思。happy number 的定义为：

如 19 就是一个 happy number :

12就不是一个happy number :

可以发现如果一个数是一个 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 上的说明是：

初始状态下，假设已知某个起点节点为节点S。现设两个指针t和h，将它们均指向S。接着，同时让t和h往前推进，但是二者的速度不同：t每前进1步，h前进2步。只要二者都可以前进而且没有相遇，就如此保持二者的推进。当h无法前进，即到达某个没有后继的节点时，就可以确定从S出发不会遇到环。反之当t与h再次相遇时，就可以确定从S出发一定会进入某个环。