Leetcode.202.Happy Number

题目

判断一个数是否happy， 如果一个数分解成各位数的平方和， 不断分解成平方和。如果最后等于1即为happy， 如果不等于1或者无限循环即不happy。

Input：19
Output： true
Explanation:  1² + 9² = 82
              8² + 2² = 68
              6² + 8²= 100
              1² + 0² + 0² = 1
Input：16
Output： false

思路

主要是要判断循环和整数越界的问题。如果最后分解的数循环的话，这些分解的数的平方和一定和之前的一个整数相等，所以用set来存储已经产生的数，来判断循环。

bool isHappy(int n) {
    unordered_set<int> m_set;
    int temp = n;
    int sum = 0;
    while (temp != 1) {
        while (temp != 0) {
            int x = temp % 10;
            sum += x * x;
            temp = temp / 10;
        }
        if (sum == 1){
            break;
        } else if (m_set.count(sum) > 0) {
            return false;
        } else {
            temp = sum;
            m_set.insert(sum);
            sum = 0;
        }
    }

    return true;
}

总结

转换思维，不要想着去判断分解出来的数组循环，比较两个数组相等太麻烦，本体比较特殊，直接比较平方和相等即可。