题目描述

编写一个算法来确定一个数字是否为快乐数字。

快乐数字是由以下过程定义的号码：

从任何正整数开始，用数字的平方和替换该号码，并重复该过程直到数字等于1（它将停留在该位置），或者它在一个不包含1的循环中无休止地变换。

以1结束这个过程的数字符合要求。

样例

Example 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

算法

(unordered_set) $O(1)$

难点在于判断是否进入死循环，这里可以用 unordered_set 来存之前已经算出过的数字。

1. 计算每位数字的平方和
2. 结果为1，则返回True
3. 结果已出现过，说明陷入死循环，返回False
4. 其他情况则重新计算每位数字的平方和，并把结果加入set

时间复杂度 $O(1)$：
(1) 首先看总共需要遍历多少个数，所有遍历的数最终会进入循环。进入环前会经过几次变换操作，每次数字 $n$ 最多变成 $81logn$，所以大于1000的数很快会缩小(n>81logn)，$2^{31}-1$ 操作四五次就会变到1000以内。考虑环内最大也是999，变化后为243，不会跳出环外，所以环内最多有1000个数。因此，环外有四五个数，环内有常数k个数。
(2) 由于用哈系表判重，所以每个数最多被遍历一次，总计算次数小于1000，所以时间复杂度是 $O(1)$。

空间复杂度 $O(n)$：
额外占用空间的是 unordered_set。

C++ 代码

class Solution {
public:
    bool isHappy(int n) {
        unordered_set<int> got;
        int m = n; // m是每次用来被拆解的数
        while(true){
            int sum = 0;
            while(m != 0){
                sum += (m % 10) * (m % 10);
                m /= 10;
            }
            if(sum == 1)
                return true;
            else if(got.find(sum)!=got.end())
                return false;
            else
                got.insert(sum);
            m = sum;
        }
    }
};

算法2

(快慢指针) $O(1)$

把sum的值看成是一个链表，那么问题转换成链表是否有环。 用快慢指针判断链表中是否有环，slow和fast最后一定会收敛到某个数字。
可以参考 LeetCode 141. Linked List Cycle。

时间复杂度 $O(1)$：
(1) 首先看总共需要遍历多少个数。把一个链表上所有的sum分成两个部分，进入环前与进入环后。进入环前会经过几次变换操作，数字 $n$ 最多变成 $81logn$，所以大于1000的数很快会缩小(n>81logn)，$2^{31}-1$ 操作四五次就会变到1000以内。考虑环内最大也是999，变化后为243，不会跳出环外，所以环内最多有1000个数。因此，环外有四五个数，环内有常数k个数。
(2) 然后看每个数最多遍历次数。快指针最多将每个数遍历2次就会和慢指针相遇。
(3) 每个数最多遍历3次，所以总计算次数小于3000，时间复杂度是 $O(1)$。

空间复杂度 $O(1)$：没有用额外的空间。

C++ 代码

class Solution {
private:
    int squareSum(int m) {
        int sum = 0;
        while(m != 0){
            sum += (m % 10) * (m % 10);
            m /= 10;
        }
        return sum;
    }
public:
    bool isHappy(int n) {
        int slow = n, fast = n;
        do {
            slow = squareSum(slow);
            fast = squareSum(fast);
            fast = squareSum(fast);
        } while(slow != fast);
        if (slow == 1) 
            return true;
        else 
            return false;
    }        
};