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. 题目简介：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网