快乐数00

题目链接

快乐数

题目描述

注意点

• 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和

解答思路

• 对于任意一个数字，其每个位置上的数字的平方和如果为1，则说明该数是快乐数，否则继续对该数字进行相同的操作。但是要注意，如果每个位置上的数字的平方和始终不为1，则一直递归下去会导致超时，但是不继续递归又不确定之后的递归过程是否会找到平方和为1，所以需要找到一个规律
• 可以确定的是除了数字较小时（数字<100），其余数字在求平方和的过程时数字都是不断减小的，甚至会减少多位，所以在不断递归求平方和的过程中，如果平方和始终不为1，则可能算出的数字是有限的，那么在某次求完平方和后，其会与之前某次求得的平方和相同，此时说明递归已经进入环了，说明该数一定不是快乐数，可直接跳出递归防止时间超时

代码

class Solution {
    public boolean isHappy(int n) {
        if (n == 1) {
            return true;
        }
        return findHappyOrCycle(n, n);
    }

    public boolean findHappyOrCycle(int slow, int quick) {
        // 慢指针每次求一次平方和
        slow = squareSum(slow);
        // 快指针每次求两次平方和
        quick = squareSum(squareSum(quick));
        if (slow == 1 || quick == 1) {
            return true;
        }
        // 快慢指针相遇，说明已经进入循环了，一定无法回到1
        if (slow == quick) {
            return false;
        }
        return findHappyOrCycle(slow, quick);
    }

    public int squareSum(int n) {
        int sum = 0;
        while (n != 0) {
            int x = n % 10;
            sum += x * x;
            n /= 10;
        }
        return sum;
    }
}

关键点

• 找到规律何时数字一定不是快乐数跳出递归