题目相关
【题目解读】
给定一个正数,判断该数是否是快乐数
。
快乐数定义:
- 将该数进行拆分,
- 拆分后的各个数值的平方求和,
- 求和的结果进行如下判断
- 该数是否为1?或者该数包含在一个循环中无休止地循环
- 如果数值是1就是
快乐数
,否则不是
ps:上面是快乐数,在遇到<10的数时,自己以为就结束了,未进行计算,实际上还需要继续进行计算。以3为例:
3
2
=
9
3^2 = 9
32=9
9
2
=
81
9^2 = 81
92=81
8
2
+
=
1
2
=
65
8^2 + =1^2 = 65
82+=12=65
6
2
+
5
2
=
61
6^2 + 5^2 = 61
62+52=61
6
2
+
1
2
=
37
6^2 + 1^2 = 37
62+12=37
3
2
+
7
2
=
58
3^2 + 7^2 = 58
32+72=58
5
2
+
8
2
=
89
5^2 + 8^2 = 89
52+82=89
8
2
+
9
2
=
145
8^2 + 9^2 = 145
82+92=145
1
2
+
4
2
+
5
2
=
42
1^2 + 4^2 + 5^2 = 42
12+42+52=42
4
2
+
2
2
=
20
4^2 + 2^2 = 20
42+22=20
2
2
+
0
2
=
4
2^2 + 0^2 = 4
22+02=4
4
2
+
0
2
=
16
4^2 + 0^2 = 16
42+02=16
1
2
+
6
2
=
37
1^2 + 6^2 = 37
12+62=37
注意这里出现了37,在第五步的时候也是37,所以后面将会一直循环。
【原题描述】原题链接
Write an algorithm to determine if a number is “happy”.
A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.
Example:
Input: 19
Output: true
Explanation:
1
2
+
9
2
=
82
1^2 + 9^2 = 82
12+92=82
8
2
+
2
2
=
68
8^2 + 2^2 = 68
82+22=68
6
2
+
8
2
=
100
6^2 + 8^2 = 100
62+82=100
1
2
+
0
2
+
0
2
=
1
1^2 + 0^2 + 0^2 = 1
12+02+02=1
【难度】Easy
Solution
以下方法误解了<10的计算方法,对于所有大于10的数据都可以通过该方法进行计算。同时10以内只有1、7才是快乐数
,所以改进后继续用该方法进行判断。
#include <vector>
class Solution {
private:
void num2value(int num, vector<int> &vec)
{
while(num / 10 != 0)
{
vec.push_back(num%10);
num /= 10;
}
if(num != 0)
vec.push_back(num);
}
public:
bool isHappy(int n) {
if(n/10 == 0)
return n == 1 or n == 7;
else
{
vector<int> vec;
num2value(n, vec);
int sum = 0;
for( int i =0; i < vec.size(); i++)
{
sum += vec[i]*vec[i];
}
return isHappy(sum);
}
}
};