快乐数

发表于 | 分类于 |
字数统计: 531 字 | 阅读时长 ≈ 2 分钟

题目描述：编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为：

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

示例 1：
输入：19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

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

快慢指针

根据题意，我们可以分析如下：

  1. 找到快乐数
  2. 没有快乐数，形成环路，造成死循环。

思路：

  • 创建一个慢指针，一次走一步，再创建一个快指针，一次走两步。
  • 当快慢指针相遇，代表形参环路，该数不是快乐数。
  • 若指针移动过程中，找到了 1，则当前数是一个快乐数。
1
2
3
4
5
6
7
8
9
10
11
12
var isHappy = function(n) {
  let slow = n, fast = getNext(n)
  while(fast !== 1 && slow !== fast) {
    slow = getNext(slow)
    fast = getNext(getNext(fast))
  }
  return fast === 1
};

var getNext = function(n) {
  return n.toString().split('').map((item) => item ** 2).reduce((a, b) => a + b)
}

复杂度分析

  • 时间复杂度：O(logn)。

    • 如果没有循环，那么快跑者将先到达 1，慢跑者将到达链表中的一半。我们知道最坏的情况下，成本是 O(2⋅logn)=O(logn)。
    • 一旦两个指针都在循环中，在每个循环中，快跑者将离慢跑者更近一步。一旦快跑者落后慢跑者一步，他们就会在下一步相遇。假设循环中有 k 个数字。如果他们的起点是相隔 k−1 的位置（这是他们可以开始的最远的距离），那么快跑者需要 k−1 步才能到达慢跑者，这对于我们的目的来说也是不变的。因此，主操作仍然在计算起始 n 的下一个值，即 O(logn)。

  • 空间复杂度：O(1)，指针需要常数的额外空间。