跳至主要內容

202. Happy Number

202. Happy Numberopen in new window

🟢   🔖  哈希表 数学 双指针  🔗 LeetCodeopen in new window

题目

Write an algorithm to determine if a number n is happy.

A happy number is a number defined by the following process:

  • Starting with any positive integer, replace the number by the sum of the squares of its digits.
  • Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
  • Those numbers for which this process ends in 1 are happy.

Return true if n is a happy number, and false if not.

Example 1:

Input: n = 19

Output: true

Explanation:

12 + 92 = 82

82 + 22 = 68

62 + 82 = 100

12 + 02 + 02 = 1

Example 2:

Input: n = 2

Output: false

Constraints:

  • 1 <= n <= 2^31 - 1

题目大意

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

「快乐数」 定义为：

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

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

解题思路

这道题需要注意循环不快乐数，比如 4 :

  1. 4^2 = 16
  2. 1^2 + 6^2 = 37
  3. 3^2 + 7^2 = 58
  4. 5^2 + 8^2 = 89
  5. 8^2 + 9^2 = 145
  6. 1^2 + 4^2 + 5^2 = 42
  7. 4^2 + 2^2 = 20
  8. 2^2 + 0^2 = 4

在第 8 步时，我们又回到了数字 4，之后的计算过程会陷入无限循环。

为了防止程序进入死循环，可以使用一个集合来记录每次变换后的结果，如果在变换的过程中遇到了已经在集合中的数字，就说明陷入了循环，这个数不是快乐数。具体的步骤如下：

  1. 定义一个变换函数：编写一个函数，接受一个数字，计算其每个位置上的数字的平方和。

  2. 使用集合记录：使用一个集合（或哈希表）来记录每次变换后的结果，以检查是否陷入循环。

  3. 迭代检查：对于给定的数字 n，不断进行变换，检查变换后的结果是否为 1 或者是否已经在集合中。如果是，说明是快乐数；如果不是，继续迭代。

  4. 返回结果：最终，如果循环结束了（即没有陷入循环），则说明这个数字不是快乐数。

  • 时间复杂度：O(logN)，由于我们使用集合记录变换后的结果，而每个数字最多会被记录一次，所以时间复杂度为 O(logN)，其中 N 是数字的大小。
  • 空间复杂度：O(logN)，使用了一个集合来记录变换后的结果，最坏情况下会包含 O(logN) 个元素。

代码

/**
 * @param {number} n
 * @return {boolean}
 */
var isHappy = function (n) {
	const getNext = (n) => {
		const arr = (n + '').split('');
		return arr.reduce((acc, num) => acc + Number(num) ** 2, 0);
	};

	let set = new Set();
	while (n !== 1 && !set.has(n)) {
		set.add(n);
		n = getNext(n);
	}

	return n == 1;
};

相关题目

相关题目
- [141. 环形链表](./0141.md)
- [258. 各位相加](https://leetcode.com/problems/add-digits)
- [263. 丑数](https://leetcode.com/problems/ugly-number)
- [1945. 字符串转化后的各位数字之和](https://leetcode.com/problems/sum-of-digits-of-string-after-convert)
- [2457. 美丽整数的最小增量](https://leetcode.com/problems/minimum-addition-to-make-integer-beautiful)
- [2507. 使用质因数之和替换后可以取到的最小值](https://leetcode.com/problems/smallest-value-after-replacing-with-sum-of-prime-factors)
- [2520. 统计能整除数字的位数](https://leetcode.com/problems/count-the-digits-that-divide-a-number)
Copyright © 2024 2xiao