快乐树，你真的快乐吗？

第202题. 快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

  • 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
  • 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
  • 如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：

1
2
3
4
5
6
7
输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

示例 2：

1
2
输入：n = 2
输出：false

思路

本题看上去是数学题？错了。看完题目，注意题目说了，会无限循环。

一说到无限循环找交点，首先应该想到快慢指针，就像链表一样，有圆定能相遇。

做法1：

​ 因此做法一的思路就很明确了，定义快慢指针，让快指针每次做两次运算，慢指针做一次运算，他们一定会在某处相遇。相遇的地点为1的话，就是快乐树了。因为做的运算的相同的，因此可以把这个运算封装成一个函数进行调用。做法1见如下C语言代码。

做法2：

​ 因为题目说了会无限循环，因此想到，在某一时刻，会出现与之前相同的数。这个数出现的位置并不让人关心。因此，可以用c++的unordered_set容器来存储当前的值。利用迭代器对容器中存储的元素进行查找，若容器中没有发现该元素，则存入。直到发现当前值等于1，或者容器中有相同元素时停止。做法2见如下C++代码。

本题还有一个重要的知识点，就是一个数n：

​ 取n%10后，就得到了个位的数值。

​ 取n/10后，就是把个位去掉后的数组（舍去最低位，n整体向右移动一位）。

c语言实现如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int get(int n){
    int sum =0;
    while(n){
        sum = sum + (n%10)*(n%10);
        n = n/10;
    }
    return sum;
}
bool isHappy(int n) {
    int fast = get(n);
    int slow = fast;
    fast = get(fast);
    while(fast != slow){
        fast = get(fast);
        fast = get(fast);
        slow = get(slow);
    }
    if(fast==1){
        return true;
    }
    return false;
}

使用c++做的时候，在力扣上运行的话，需要单独定义一个get函数，单独对变量值进行处理，否则程序会运行超时。

c++实现如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int get(int n){
        int sum =0;
        while(n){//循环取得最后一位
            sum = sum+ (n%10)*(n%10);
            n = n/10;
        }
        return sum;
    }
    bool isHappy(int n) {
        unordered_set<int> hash;
        int sum =0;
        while(1){
            sum = get(n);            
            if(sum == 1){
            return true;
            }
            if(hash.find(sum) != hash.end()){
                return false;
            }
            else{
                hash.insert(sum); 
            }
            n = sum;
        }
    }
};