LeetCode 202 快乐数

LeetCode 202 快乐数 题目跳转链接

具体实现思路如下：

1. 实现一个函数getSum，用来计算一个数各个位上的数字的平方和。具体实现就是对这个数进行除十操作和取余操作，对每个位上的数字平方后累加到总和中。

2. 在一个while循环中，不断调用getSum函数，直到计算出1或者陷入无限循环为止。同时，使用哈希表unordered_set记录每次计算出来的数字，如果在后续的计算过程中出现了这个数字，说明会陷入无限循环，就可以直接返回false。

3. 如果计算出来的数字是1，那么就返回true，这个数就是快乐数。

整体时间复杂度为O(logn)，因为一个n位的数，最多需要计算n次，每次计算的复杂度为O(logn)。空间复杂度也为O(logn)，因为要记录每个产生的数字。

class Solution 
{

int getSum(int n)
{
    int sum=0;
    while(n)
    {
        sum+=(n%10)*(n%10);
        n/=10;
    }
    return sum;
}


public:
    bool isHappy(int n) 
    {
        unordered_set<int> set;//记录陷入无限循环的数值

        while(1)
        { 
            int sum=getSum(n);
            if(sum==1)
            { return true;}

            //如果这个sum曾经出现过，说明已经陷入循环
            if(set.find(sum)!=set.end())
            {
                return false;
            }
            else
            {
                set.insert(sum);
            }
            n=sum;
        }
    }
};

(感觉还是不太好记捏..考到不一定会写...)