LeetCode OJ 之 Happy Number （happy数）

题目：

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

• 12 + 92 = 82
• 82 + 22 = 68
• 62 + 82 = 100
• 12 + 02 + 02 = 1

思路：

1、把计算过的数保存下来，下次计算后判断结果是否在计算过的结果里。如果存在，则说明计算存在循环，就不可能得到1，即不是happy数。

2、由上面的方法可以联想链表中是否有环的问题：http://blog.csdn.net/u012243115/article/details/41891075。这一题同样可以用那种方法。一个数每次计算一次，另一个数每次计算两次。如果是happy数，则它们两个不会相遇。如果不是happy数，则它们肯定会相遇。

代码：

class Solution {
public:
    bool isHappy(int n) 
    {
        set<int> hasCal;//保持已经计算过的数
        hasCal.insert(n);
        while(true)
        {
            n = cal(n);
            if(n == 1)
                return true;
            if(hasCal.find(n) != hasCal.end())
                return false;
            hasCal.insert(n);
        }
        return false;
    }
    int cal(int n)
    {
        int result = 0;
        while(n)
        {
            int tmp = n % 10;
            result += tmp * tmp;
            n = n / 10;
        }
        return result;
    }
};

优化空间：

class Solution {
public:
    bool isHappy(int n) 
    {
        int once = n;
        int twice = n;
        while(true)
        {
            once = cal(once);
            if(once == 1)
                return true;
            twice = cal(cal(twice));
            if(twice == 1)
                return true;
            if(once == twice)
                return false;
        }
        return false;
    }
    int cal(int n)
    {
        int result = 0;
        while(n)
        {
            int tmp = n % 10;
            result += tmp * tmp;
            n = n / 10;
        }
        return result;
    }
};