题目链接：Happy Number

Write an algorithm to determine if a number is “happy”.

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example: 19 is a happy number

1^2 + 9^2 = 82 
8^2 + 2^2 = 68 
6^2 + 8^2 = 100 
1^2 + 0^2 + 0^2 = 1

这道题的要求是判断一个数是不是”happy”的。关于”happy”数字的定义：从这个数字（正整数）开始，用其各个数位上数字的平方和替换这个数字，直到等于1或者出现重复。如果最后等于1说明是”happy”数组。

简单模拟，用Hash记录出现过的数组，用以判断是否出现环。

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

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

可以注意到，每次生成的数字，可以构成一个链表，而且要求找环或者是否等于1，这可以利用链表找环的思路（也就是快慢指针）进行找环，这样可以节省下Hash表的开销，将空间复杂度将为O(1)，代码略。