快乐数
题目描述
编写一个算法来判断一个数 n 是不是快乐数。 如果 n 是快乐数就返回 True ;不是,则返回 False 。
「快乐数」定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为 1,也可能是 无限循环,但始终变不到 1。如果 可以变为 1,那么这个数就是快乐数。
解题思路
很明显,要求n是否是快乐数,就是要判断每一位的平方然后求和,判断和是否为1,但是需要判断每一个数是否在之前已经出现过,如果出现过,说明陷入了无限循环,那么一定不能变成1。
代码如下
leetcode上面只要求写函数部分,但是我还是写一下整个的过程。
只有函数部分
class Solution {
public:
map<int,int>p;
bool isHappy(int n) {
int ans = n;
while(!p[ans]) {
p[ans] = 1;//说明一下为啥要在这个地方标记这个数出现过,如果是在下面每次求出新的ans之后进行标记,那么就不能够在进入循环了,因为此时ans已经被标记出现过了
int cnt = ans;
ans = 0;//因为ans要存储算出来的各位平方和,要先初始化为0
while(cnt > 0) {
ans += (cnt%10)*(cnt%10);
cnt /= 10;
}
if(ans == 1) return true;
}
return false;
}
};
总的代码
#include<bits/stdc++.h>
using namespace std;
map<int,int>p;
bool isHappy(int n){
int ans = n;
while(!p[ans]) {
p[ans] = 1;//说明一下为啥要在这个地方标记这个数出现过,如果是在下面每次求出新的ans之后进行标记,那么就不能够在进入循环了,因为此时ans已经被标记出现过了
int cnt = ans;
ans = 0;//因为ans要存储算出来的各位平方和,要先初始化为0
while(cnt > 0) {
ans += (cnt%10)*(cnt%10);
cnt /= 10;
}
if(ans == 1) return true;
}
return false;
}
int main() {
int n;
scanf("%d",&n);
printf("%d",isHappy(n));
}