【LeetCode】202. 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 number时是否陷入循环。一种是把每一步算出的平方和插入Hash Set中，如果已经存在这个数了，说明已经进入了循环状态，则该数不是happy number。

另一种方法就是把平方和保存到数组（vector）中。然后每次遍历地去寻找该平方和是否曾经出现过。

虽然用Hash Set是O(1)，对vector遍历是O(n)，但是因为数字不多，因此用遍历的方法速度也很快。

纯数学方法：

关于happy number的循环序列有数学证明，我们可以通过判断平方和是否出现“4”来判断是否有循环。具体证明可以参看这篇文章。

代码：

下面给出利用vector遍历的方法：

class Solution {
public:
    bool isHappy(int n) {
        vector<int> nums;
        int result;
        while (true) {
            if (n == 1) return true;
            nums.push_back(n);
            result = 0;
            while (n != 0) {
                result += (n % 10) * (n % 10);
                n = n / 10;
            }
            for (int i = 0; i < nums.size(); ++i) {
                if (nums[i] == result) return false;
            }
            n = result;
        }
    }
};