快乐数

题目

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

快乐数定义为:

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

示例

输入: 19 pnpm 输出: true

解释:

• 1²+ 9² = 82
• 8² + 2² = 68
• 6² + 8² = 100
• 1² + 0² + 0² = 1

题解

一个数字, 按每个位置求平方和, 得到的新数字再次按每个位置求平方和, 这样往复计算, 总会遇到重复的. 所以可以用 Hash 表.

比如说 12 -> 5 -> 25 -> 29 -> 85 -> 89 -> 145 -> 42 -> 20 -> 4 -> 16 -> 37 -> 58 -> 89.

JavaScript - 快慢指针

如果做过 141. 环形链表, 应该一眼看出这是一个环状结构没跑了, 所以可以使用快慢指针.

/**
 * @param {number} n
 * @return {boolean}
 */
var isHappy = function (n) {
  let fast = n,
    slow = n

  do {
    slow = compute(slow)
    fast = compute(compute(fast))
  } while (fast !== slow)

  return slow === 1
}

/**
 * @param {number} n
 * @return {number}
 */
var helper = function (n) {
  let squareSum = 0

  while (n) {
    squareSum += Math.pow(n % 10, 2)
    n = Math.floor(n / 10)
  }

  return squareSum
}

JavaScript - Hash Table

/**
 * @param {number} n
 * @return {boolean}
 */
var isHappy = function (n) {
  const set = new Set([n])

  while (n !== 1) {
    n = calculate(n)
    if (set.has(n)) return false
    set.add(n)
  }

  return true
}

/**
 * @param {number} n
 * @return {number}
 */
var calculate = function (n) {
  let squareSum = 0

  while (n) {
    squareSum += Math.pow(n % 10, 2)
    n = Math.floor(n / 10)
  }

  return squareSum
}