哈希
解题思路
求和的过程中，sum 会重复出现，当遇到了要快速判断一个元素是否出现集合里的时候，就要考虑 哈希 了；
如果 sum 在哈希中出现过，证明已陷入无限循环了；
复杂度
-
时间复杂度：
O(logn)； -
空间复杂度：
O(logn)；
代码实现
var isHappy = function (n) {
let hash = new Set();
while (n !== 1) {
n = getSum(n);
if (hash.has(n)) return false; // 死循环了，终止运行
hash.add(n);
}
return n === 1;
};
var getSum = function (n) {
let sum = 0;
while (n > 0) {
sum += (n % 10) ** 2;
n = Math.floor(n / 10);
}
return sum;
}
快慢指针
解题思路
由于求和的过程中，有可能会出现重复值，会形成一个环，那么就可以借鉴 leetcode🧑💻 141. 环形链表 的解题方式；
利用快慢指针 fast 和 slow ，由于这里不是指针，向下移动相当于
getSum(n)：
- 如果他们最终相遇则说明存在环，则进一步说明出现了死循环，则不是一个快乐数；
- 如果他们没有相遇，结果为 1 则是一个快乐数
代码实现
let isHappy = function (n) {
// 1. 定义快慢指针
let slow = n;
let fast = getSum(n);
// 2. 判断是否有环
while (fast !== 1) {
slow = getSum(slow);
fast = getSum(getSum(fast));
if (slow === fast) return false; // 有环
}
return true;
}
let getSum = function (n) {
let sum = 0;
while (n > 0) {
sum += Math.pow(n % 10, 2);
n = Math.floor(n / 10);
}
return sum;
}
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 88. 合并两个有序数组
上一篇
评论
