北京北站wordpress小工具源码

leetcode202. 快乐数

编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：
对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：
输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

示例 2：
输入：n = 2
输出：false

使用 双指针，即快慢指针。
“快指针” 每次走两步，“慢指针” 每次走一步，当二者相等时，即为一次序列周期。接下来看是不是因为 1 引起的循环，是就是快乐数，否则不是快乐数。

getNext 函数：
这个函数接受一个整数 n 作为参数。
它的作用是计算 n 的各位数字的平方和。例如，如果 n 是 123，那么 getNext 将计算 1 * 1 + 2 * 2 + 3 * 3 的结果。
它通过一个循环来实现，循环中将 n 除以 10 并取余数得到最低位的数字，然后将这个数字的平方加到 totalSum 变量上。然后，将 n 更新为去掉最低位后的数字，继续循环直到 n 为 0。
最终，函数返回 totalSum 的值。

isHappy 函数：
这个函数同样接受一个整数 n 作为参数。
它的目的是判断 n 是否是一个快乐数。快乐数是一个正整数，其各位数字的平方和循环计算后最终会达到 1。
函数使用快慢指针（或称为龟兔赛跑算法）来实现。慢指针 slow 每次调用 getNext 函数计算当前数的平方和，而快指针 fast 则调用两次 getNext，即计算当前数的平方和的平方和。
当 fast 和 slow 相遇（即 fast 等于 slow）或者 fast 达到 1 时，循环结束。
如果 fast 等于 1，说明 n 是一个快乐数，函数返回 true；否则，返回 false。

具体代码实现如下：

class Solution {
public:int getNext(int n) {int totalSum = 0;while (n > 0) {int d = n % 10;n = n / 10;totalSum += d * d;}return totalSum;}bool isHappy(int n) {int slow=n;int fast=getNext(n);while(fast!=1 && slow !=fast){slow=getNext(slow);fast=getNext(getNext(fast));}return fast==1;}
};