正经题解｜ 快乐数

题目分析

对于一个非负整数，每次将该数替换为它每个位置上的数字的平方和。重复这个过程，直到能变换为 $1$，也可能是 无限循环。如果能变换为 $1$，那么这个数即为快乐数。

可以先试一下某个数，找它的变化路径，并将其打印，会发现 无限循环 中会出现很多重复到达的值，这样子就形成了一个圈，所以永远都走不到 $1$。所以在变化的过程中，如果出现重复的值，则说明形成了一个圈，那么这个数就一定不是一个快乐数。

AC代码

#include <bits/stdc++.h>
using namespace std;
bool isHappy(int n) {
    map<int,int> vis;
    while(n != 1 && vis.count(n) == 0) {
        vis[n] = 1;
        int x = 0;
        while(n) {
            x += (n % 10) * (n % 10);
            n/=10;
        }
        n = x;
    }
    return n == 1;
}
int main() {
    int n;
    cin >> n;
    if (isHappy(n)) {
        cout << "YES" << endl;
    }else {
        cout << "NO" << endl;
    }
    return 0;
}

复杂度分析

最大是 5 个位数上都是 $9$，即 $99999$，下一个数就跳到了 $405$。接着的变化路径就是 $41$ -> $17$ -> $50$ -> .... 接着已经是在 $3$ 位数的范围内了，所以也只需要 $405$ 范围内的快乐数的答案就行了，这块如果预处理完后就是 $O(1)$ 了。

接着数位分离得出下一个值的这个while，很容易看出来是一个 $O(log_{10}n)$ 的复杂度。

所以最终的复杂度为：$O(logn)$。