编写一个算法来判断一个数 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
- 注：1 <= n <= 231 - 1
解题思路如下：
非快乐数会造成一个循环；
类似如图：
我们选择使用快慢指针来解决，流程如下：
- 创建一个慢指针，一次走一步，再创建一个快指针，一次走两步。
- 当快慢指针相遇，代表形参环路，该数不是快乐数。
- 若指针移动过程中，找到了 1，则当前数是一个快乐数。
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) // } };
快慢指针与哈希方法相比，不用创建集合来储存每次循环的数，所以减少了内存的消耗，是更好的选择~~
以上，便是本篇分享；
我是掘金安东尼，输出暴露输入，技术洞见生活，再会。
