Keshawn_lu's Blog

Leetcode 202. 快乐数

字数统计: 198阅读时长: 1 min
2020/04/30 Share

题目简介:

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。如果 可以变为 1,那么这个数就是快乐数。

如果 n 是快乐数就返回 True ;不是,则返回 False 。

示例:

1
2
3
4
5
6
7
输入:19
输出:true
解释:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

思路:因为每个数最后的结果,要么是1,要么是无限循环,以下是大佬的证明

我们需要证明:

以下是证明:

注意最后一步放缩,分子向上放(ai <= 9),分母向下缩(m位数肯定是大于等于m位数最小的那个数)。

好了,这就证明了不会有一个一直增长的链表,而且在 n 非常大的时候,通过 squareSum(n)操作会急剧变小。

通过上述操作我们知道了只有两种情况的可能,所以我们可以设置一个set,来存储每次平方和后的结果,如果在某次平方和后得到的结果在之前已经遇到过了,说明就陷入了循环,返回false即可,如果最后的结果为1,即返回true,说明是快乐数。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:

int SquareSum(int n){

int sum = 0;

while(n != 0){

sum += pow(n % 10, 2);

n /= 10;
}
return sum;
}

bool isHappy(int n) {

set<int> hashset;

if(n == 1)
return true;

hashset.insert(n);


while(n != 1){

n = SquareSum(n);
//.second 插入成功返回true,插入失败返回false
if(hashset.insert(n).second == false)
return false;
}

return true;
}
};
CATALOG
  1. 1. 题目简介: