「这是我参与2022首次更文挑战的第11天,活动详情查看:2022首次更文挑战」
编写一个算法来判断一个数 n
是不是快乐数。
什么是快乐数?
对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。 然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。 如果这个过程 结果为 1,那么这个数就是快乐数。
如果 n
是快乐数,函数返回 true
;不是,则返回 false
。
示例 1:
输入:n = 19
输出:true
解释:
1² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1² + 0² + 0² = 1
示例 2:
输入:n = 2
输出:false
解题思路如下:
非快乐数会造成一个循环;
类似如图:
我们选择使用快慢指针来解决,流程如下:
JavaScript 实现:
let getNext = function (n) {
return n.toString().split('').map(i => i ** 2).reduce((a, b) => a + b);
}
let isHappy = function (n) {
let slow = n;
let fast = getNext(n);
while(fast !== 1 && fast !== slow){
slow = getNext(slow);
fast = getNext(getNext(fast));
}
return fast === 1;
};
除了快慢指针,还有常用的哈希方法:
/**
* 解法1:哈希法
* 缺点是用到哈希集合,空间复杂度过高
*/
const getSum = n => {
let sum = 0
while (n) {
sum += (n % 10) ** 2
n = Math.floor(n / 10)
}
return sum
}
var isHappy = function (n) {
// Set写法
let ret = new Set()
while (1) {
if (ret.has(n)) return false
if (n === 1) return true
ret.add(n)
n = getSum(n)
}
// Map写法
// let ret = new Map()
// while (1) {
// if (ret.has(n)) return false
// if (n === 1) return true
// ret.set(n, 1)
// n = getSum(n)
// }
};
快慢指针与哈希方法相比,不用创建集合来储存每次循环的数,所以减少了内存的消耗,是更好的选择~~
以上,便是本篇分享;
我是掘金安东尼,输出暴露输入,技术洞见生活,再会。