正经题解| 快乐数
2024-07-22 10:50:06
发布于:浙江
45阅读
0回复
0点赞
题目分析
对于一个非负整数,每次将该数替换为它每个位置上的数字的平方和。重复这个过程,直到能变换为 ,也可能是 无限循环。如果能变换为 ,那么这个数即为快乐数
。
可以先试一下某个数,找它的变化路径,并将其打印,会发现 无限循环 中会出现很多重复到达的值,这样子就形成了一个圈,所以永远都走不到 。所以在变化的过程中,如果出现重复的值,则说明形成了一个圈,那么这个数就一定不是一个快乐数。
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 个位数上都是 ,即 ,下一个数就跳到了 。接着的变化路径就是 -> -> -> .... 接着已经是在 位数的范围内了,所以也只需要 范围内的快乐数的答案就行了,这块如果预处理完后就是 了。
接着数位分离得出下一个值的这个while
,很容易看出来是一个 的复杂度。
所以最终的复杂度为:。
这里空空如也
有帮助,赞一个