202. 快乐数

🟢   🔖  哈希表 数学 双指针  🔗 力扣 LeetCode

题目

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	环形链表	[✓]	哈希表 链表 双指针
258	各位相加		数学 数论 模拟
263	丑数		数学
1945	字符串转化后的各位数字之和		字符串 模拟
2457	美丽整数的最小增量		贪心 数学
2507	使用质因数之和替换后可以取到的最小值		数学 数论 模拟
2520	统计能整除数字的位数		数学