LeetCode 202. 快乐数

目录

• 相似题目
• 原题
• 题目解析
• 算法原理
• 代码实现

相似题目

环形链表
环形链表 II

原题

快乐数

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

「快乐数」 定义为：

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

如果 n 是快乐数就返回 true ；不是，则返回 false 。

示例 1：
输入：n = 19
输出：true

示例 2：
输入：n = 2
输出：false

题目解析

题目要求我们对一个正整数进行计算，计算时，取它每一位上的数字，进行平方然后计算和，如果最后结果是 1，那么就是快乐数，比如示例 1：

也有可能无限循环最后结果永远不为 1，那么它就不是快乐数，比如示例 2：

算法原理

经过对题目给出的示例观察后发现，在计算快乐数的过程中，可能会出现环（或称数字的循环），在环内如果算出来的数一直都是 1，那么肯定是快乐数，如果算出来的数一直取不到 1，那么就不是快乐数了，因此，我们可以借助两个指针 slow 和 fast (这里的指针非真正意义上的指针，实际上是为保存计算出来的值而设定的两个变量)，使用快慢指针的方式，让 slow 移动一步，fast 移动两步，当 slow 和 fast 相遇时(计算出的值相等时)，肯定是在环内，此时判断计算出来的值是否为 1 即可

示例 1：

示例 2：

代码实现

1class Solution {
2public:
3    int Sum(int n)
4    {
5        int sum = 0;
6        while (n)
7        {
8            int last = n % 10;
9            sum += last * last;
10            n /= 10;
11        }
12        return sum;
13    }
14
15    bool isHappy(int n) {
16        int slow = n;
17        int fast = Sum(n);
18
19        while (slow != fast)
20        {
21            slow = Sum(slow);
22            fast = Sum(Sum(fast));
23        }
24
25        return slow == 1;
26    }
27};
28

《LeetCode 202. 快乐数》 是转载文章，点击查看原文。