编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。如果 可以变为 1,那么这个数就是快乐数。
如果 n 是快乐数就返回 True ;不是,则返回 False 。
解题思路:用快慢指针可以解决这种问题,定义一个求一个数每个位数上的数字的平方和的函数,然后慢指针接收快指针的结果,快指针每次不断的根据题目要求求它下一个需要求的算数和,这样最后如果快指针和慢指针相同了,每个数字都会根据 各位平方和 指向另一个数字,所以从任意数字开始进行 各位平方和 的迭代操作,就相当于在链表上游走。如果**无限循环 **但始终变不到 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; } }