LeetCode 202. 快乐数

快乐数

题目链接 202. 快乐数

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

「快乐数」 定义为：

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

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

示例 1：

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

题目解释

什么是快乐数,就是将我们数的每一位数计算他的平方,判断他是否是1,如果不是是1,我们持续上面的操作,直到我们遇到1,那么这个数就是快乐数.如果我们无法得到1,那么就是不快乐的.

算法原理

下面我们用两个例子来解析我们如何解决这道题目.

• val是快乐数
• val不是快乐数

我们发现,无论val是不是快乐数,我们都会陷入下面的情况.

这里很容易的想到我们在链表中判断是是否存在环.那么就可以使用快慢指针了.

• 快指针走2步
• 慢指针走1步

细节补充

• 快慢指针中快指针走2步,慢指针走1步为何可以判断有环,这里不再解释,可以看看链表相关的
• 我们上面经过若干次判断,难道一定会生成环的情况吗?不能是一条直线吗
• 如何快速转换val的值

如果我们分析了题目中的快乐数的第二条定义,那么我们可以隐约猜到一定会存在环.这里也是可以简单的说明一下.我们说下鸽巢原理

鸽巢原理一般含义为:如果每个抽屉代表一个集合，每一个苹果就可以代表一个元素，假如有n+1个元素放到n个集合中去，其中必定有一个集合里至少有两个元素.

我们看一下我们的数据范围

• 1 <= n <= 2³¹ - 1

这里我们会发现,对于我们每一次的val经过转换,都会出现在[0, 810]的结果内,只要我们转换超过810次,那么一定会出现重复的元素.

解决我们如何一次的转换val的值,很简单,提取每一位的值,经过平方后保存下来

int bitSum(int val)
{
    int sum = 0;
    while (val)
    {
      int ret = val % 10;
      sum += ret * ret;
      val /= 10;
    }
    return sum;
}
1
2
3
4
5
6
7
8
9
10
11

代码编写

class Solution
{
public:
  int bitSum(int val)
  {
    int sum = 0;
    while (val)
    {
      int ret = val % 10;
      sum += ret * ret;
      val /= 10;
    }
    return sum;
  }
  bool isHappy(int n)
  {
    int slow = n;
    int fast = n;
    while (true)
    {

      slow = bitSum(slow);
      fast = bitSum(bitSum(fast));
      if (slow == fast)
        break;
    }

    return slow == 1;
  }
};
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