【202】快乐数

【202】快乐数 场景：

题目：快乐数
（1）需求：编写一个算法来判断一个数 n 是不是快乐数，如果 n 是快乐数就返回 true ；不是，则返回 false ；
（2）定义：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环但始终变不到 1；如果 可以变为 1，那么这个数就是快乐数；
（3）示例：
示例 1：
输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
示例 2：
输入：n = 2
输出：false
（4）提示：
1 <= n <= 231 - 1

---

思路：

（1）根据需求，先求平方和，接着判断该数是否是快乐数，如果不是就继续上一层判断，在这里我想使用递归来解决这个问题，但是在测试时发现递归并不能很好的解决无限循环的问题，例如下面的代码一，当测试案例是19时，可以正确通过，但当案例是2时，会进入无限循环；同时再观察无限循环细节时，会发现同一个平方和多次出现；于是采取其他的方法来处理。
（2）C++ 11 为 STL 标准库增添了 4 种无序（哈希）容器，其中之一是unordered_set 容器，和 set 容器唯一的区别就在于 set 容器会自行对存储的数据进行排序，而 unordered_set 容器不会。
（3）unordered_set特性：不再以键值对的形式存储数据，而是直接存储数据的值；容器内部存储的各个元素的值都互不相等，且不能被修改；不会对内部存储的数据进行排序；
（4）unordered_set中有4个参数，这里我们只使用第一个参数key,同时这个参数没有默认值；
（5）unordered_set可以直接通过构造方式创建对象；count（key）返回的是set中值为key元素的个数；insert(key)表示将key值填入set中；
（6）通过unordered_set，可以很好的解决陷入无限循环的问题，在容器中寻找出现过的平方和，找到便跳出循环，找不到将其添加到容器中；

---

代码实现：

代码一（失败：陷入无限循环）

#include 
#include 
#include 
using namespace std;
class Solution
{
public:
    // 寻找快乐数
    bool isHappy(int n)
    {
        bool flag = false;
        // 求平方和
        int sum_of_squares = 0;
        while (n > 0)
        {
            int d = n % 10;
            n /= 10;
            sum_of_squares += pow(d, 2);
        }
        // cout << "sum_of_squares = " << sum_of_squares << endl;
        // 判断快乐数
        if (sum_of_squares != 1)
        {
            // 这里可能无限循环，导致程序永远出不来，无法返回值
            isHappy(sum_of_squares);
        }
        flag = true;
        return flag;
    }
};

代码二（成功：采用unordered_set容器）

#include 
#include 
using namespace std;
class Solution
{
public:
    bool isHappy(int n)
    {
        // 创建一个空的 unordered_set 容器，存储 int 类型的值
        unordered_set set;
        // 循环判断 是否为快乐数 直到满足快乐数的退出
        while (n != 1)
        {
            // 求平方和
            int sum_of_squares = 0;
            while (n)
            {
                int d = n % 10;
                sum_of_squares += pow(d, 2);
                n /= 10;
            }
            n = sum_of_squares;
            // 在 set 容器中找是否有相同的值存在
            if (set.count(n))
                break;
            set.insert(n);
        }
        return n == 1 ? true : false;
    }
};