202 快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为  1，那么这个数就是快乐数。

如果 n 是快乐数就返回 True ；不是，则返回 False 。

示例：
输入：19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

题目分析：

只会有以下可能的情况：

• 最终得到1
• 最终走进循环
• 数越来越大趋近于无穷（但其实不可能，因为即使是最大的三位数999的下一个数也只能是243

所以只有前两种情况可能出现，只需要判断最后是否进入循环即可。即是否出现过已经出现过的数字。分析到这里自然会想到用哈希（HashSet）

代码

分两部分实现
首先判断一个数字对应的下一个数是什么，这很容易，我们只需要提取出这个数字的每个位即可，之前也有过类似的题目。

//此函数用来获得n的每个位上的数字的平方和
public int getsum(int n){
    int sum = 0;
    while(n > 0){
        sum += (n%10) * (n%10);
        n = n / 10;
    }
    return sum;
}

其次，判断这个数是否已经在HashSet中，若不在将它加入，若要放入的数字已经在HashSet中，说明走进了循环，返回false

public boolean isHappy(int n) {
    //只有两种情况，一种循环到1，另一种循环到已经到过的一个数，进入了一个环。前者为true，后者为false
    Set<Integer> seen = new HashSet<>();
    while(n != 1 && !seen.contains(n)){
        seen.add(n);
        n = getsum(n);
    }
    //退出循环有两种情况
    //1.已经循环到了1.
    //2. 循环到了曾经走过的点
    return n==1;
}

注意对于HahSet的操作:

• 加入元素：seen.==add==(n)
• 检查一个元素n是否在seen中：seen.==contains==(n)。此步只需要O(1)的时间复杂度

时间复杂度和空间复杂度:
都是O(logn)

另一种方法：快慢指针法

既然上述分析时考虑到了是否存在循环的问题，则可以用链表的思想来考虑。一个节点计算其各位平方再求和的过程可以类似于链表用next指针指向下一个节点。
于是可以用快慢指针检查是否出现了环

public boolean isHappy(int n) {
    int slowRunner = n;
    int fastRunner = getNext(n);
    while (fastRunner != 1 && slowRunner != fastRunner) {
        //以下两步可看作
        //slowRunner = slowRunner.next;
        //fastRunner = fastRunnr.next;
        slowRunner = getNext(slowRunner);
        fastRunner = getNext(getNext(fastRunner));
    }
    return fastRunner == 1;
}