leetcode 202

链接：力扣 。

题目：

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

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

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

示例1：

输入：19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

思路：

数学的逻辑很清晰。首先把数字 n 的各位取出来求平方和sum，判断sum是否为1，如果为1则返回true；否则令 n 等于sum，循环重复相同的过程。

在这样的设计下有一个问题，只有当sum为1时才会返回true跳出循环，如果sum始终变不到1就会陷入死循环。我们还需要设置一个哈希表来存储之前求过的sum值，当遇到当前的sum在哈希表中已经存在时，说明陷入了无限循环，sum不可能再变成1，这个时候我们就可以返回false退出循环了。

本题中的哈希表不能有重复值，故选择unordered_set。

参考代码：

class Solution {
public:
    bool isHappy(int n) {
        unordered_set<int> hashMap;
        while (1) {
            int sum = 0;
            while (n) {
                sum += (n % 10) * (n % 10);
                n /= 10;
            }
            if (sum == 1) {
                return true;
            }
            if (hashMap.find(sum) != hashMap.end()) {
                return false;
            }
            hashMap.insert(sum);
            n = sum;
        }
    }
};