202. Happy Number
202. Happy Number
题目
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
,之后的计算过程会陷入无限循环。
为了防止程序进入死循环,可以使用一个集合来记录每次变换后的结果,如果在变换的过程中遇到了已经在集合中的数字,就说明陷入了循环,这个数不是快乐数。具体的步骤如下:
定义一个变换函数:编写一个函数,接受一个数字,计算其每个位置上的数字的平方和。
使用集合记录:使用一个集合(或哈希表)来记录每次变换后的结果,以检查是否陷入循环。
迭代检查:对于给定的数字
n
,不断进行变换,检查变换后的结果是否为1
或者是否已经在集合中。如果是,说明是快乐数;如果不是,继续迭代。返回结果:最终,如果循环结束了(即没有陷入循环),则说明这个数字不是快乐数。
- 时间复杂度:
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)