一个“快乐数”定义:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为1,也可能是无限循环但始终变不到1.如果可以变为1,那么这个数就是“快乐数“。
示例:
输入:19
输出:true
1^2+9^2 = 82
8^2+2^2 = 68
6^2+8^2 = 100
1^2+0^2+0^2=1
每个数字都会根据各位平方和指向另一个数字,所以从任意数字开始进行 各位平方和 的迭代操作,就相当于在链表上游走。如果无限循环但始终变不到 1,那说明肯定是链表游走到了环。
环->快慢指针
public class Solution {
public int squareSum(int n) {
int sum = 0;
while(n > 0){
int digit = n % 10;
sum += digit * digit;
n /= 10;
}
return sum;
}
public boolean isHappy(int n) {
int slow = n, fast = squareSum(n);
while (slow != fast){
slow = squareSum(slow);
fast = squareSum(squareSum(fast));
}
return slow == 1;
}
}