202. 快乐数.md

Meta

• alias:
• parent :: [[algo-哈希]]
• siblings ::
• child :: [[如何取一个整数各位置上的数字进行计算]]
• refs: https://leetcode.cn/problems/happy-number/

---

class Solution {
    public boolean isHappy(int n) {
        // 要点：
        // 1 无限循环即计算过程中存在重复 A -> ... -> A
        // 2 n 在计算过程中不会无限变大，4 位数字的任意 n 计算后会降到 3 位(int 最大为 10 位数字)
        // 此题解法为：举例发现规律
        Set<Integer> set = new HashSet<>();
        int res;
        while ((res = calc(n)) != 1) {
            if (set.contains(res)) {
                return false;
            } else {
                set.add(res);
                n = res;
            }
        }
        return true;
    }

    // 编程技巧：取一个整数的每个位置上的数字进行计算
    private int calc(int n) {
        // 每次取个位上的数字 即 n % 10
        int sum = 0;
        while (n != 0) {
            int d = n % 10;
            sum += d * d;
            n = n / 10;
        }
        return sum;
    }
}

public boolean isHappy(int n) {
    // 举例发现计算过程类似判断链表是否有环，故可利用双指针
    int slow = n, fast = n;
    do {
        fast = calc(calc(fast)); // fast 走两步
        slow = calc(slow); // slow 走一步
    } while (slow != fast);
    // 若为快乐数即 fast 为 1，calc(fast) 仍然为 1
    return slow == 1;
}