LeetCode 202. 快乐数

题目链接：https://leetcode.cn/problems/happy-number/

思路如下：

由题目可知，$n$ 的取值在 $[1,2^{31}-1]$ 的范围内，在 $[1,2147483647]$ 这个区间里面，平方和最大的数是 $1999999999$，也就是说，最大的平方和为 $81\ast 9+1=730$，超过 $730$ 次操作就一定会出现重复数字，即陷入了环中。

$n$ 是快乐数：

$n$ 不是快乐数：

使用“快慢指针”思想找出循环：“快指针”每次走两步，“慢指针”每次走一步，当两者相等时，判断是不是因为 $1$ 引起的循环，是的话就是快乐数，否则不是快乐数。

C++代码如下：

class Solution {
public:
    int get(int x) {
        int res = 0;
        while (x) {
            int t = x % 10;
            res += t * t;
            x /= 10;
        }
        return res;
    }

    bool isHappy(int n) {
        int slow = n, fast = n;

        do {
            slow = get(slow);
            fast = get(get(fast));
        } while (fast != slow);

        return fast == 1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23