202. 快乐数

Problem: 202. 快乐数

数学规律

本题中，虽然可以很容易想到要检测是否出现环，但是实际上还应该考虑到，会不会出现无限发散的情况。

由于每个位置上都填9是给定位数下的最大值，我们从少位到多位依次检验，可以发现到了999之后，会回到243这个值，意味着如果从1开始，数不可能大于999。

而给定的数据范围是十的九次方数量级，当有10个9时，其位数平方和可得不会大于810。因此在题目给定的输入内，我们可以知道除了给定数，其他得到的数不会超过999。

知道了这个，我们就可以开辟一个固定空间的数组来作为哈希表，比使用动态哈希表时间要少。

快慢指针

前面我们使用哈希表是为了检验有没有重复出现的数，而本题的数据结构类似于一个没有空间存储的链表，需要检测有没有环。用到快慢指针的思想，我们可以用来检测链表是否有环出现。

具体来说，我们设定一个快跑者和一个慢跑者，快跑者每次跑两步，慢跑者每次跑一步，已知他们会沿着同样的赛道奔跑（用同一个函数求得链表的下一个值），如果跑道有环，那么他们肯定会在某一时刻相遇，否则快跑者会先完成。我们在快跑者到达1或者他们相遇时结束循环。

这样我们最后只需要检测快跑者是否到达1即可。

Code

[]

class Solution {
    public boolean isHappy(int n) {
        HashSet<Integer> s = new HashSet<>();
        while (!s.contains(n)) {
            s.add(n);
            int next = 0;
            while (n != 0) {
                int v = n % 10;
                next += v * v;
                n /= 10;
            }
            n = next;
            if (n == 1) return true;
        }
        return false;
    }
}