跳至主要內容

202. 快乐数


202. 快乐数

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