202. Happy Number

Easy

Description

判斷一個數字 n 是否為「快樂數」。快樂數的定義：反覆將數字替換為其各位數字的平方和，最終會得到 1。如果進入無限循環且不會到達 1，則不是快樂數。

Example:

Input: n = 19 Output: true (1^2 + 9^2 = 82 -> 8^2 + 2^2 = 68 -> … -> 1)

Intuition#

核心思路：這是一個鏈結串列找環問題——用快慢指標檢測是否會進入循環。

反覆計算各位數字平方和，結果要嘛收斂到 1，要嘛進入循環
用 HashSet 記錄看過的數字可以偵測循環，但需要 O(n) 空間
Floyd 快慢指標法：慢指標算一次、快指標算兩次，若相遇則有環

Approaches#

1: HashSet 偵測循環#

概念: 用 Set 記錄每次計算的結果，如果出現重複表示進入循環
時間複雜度: O(log n) - 數字會快速縮小
空間複雜度: O(log n) - Set 儲存中間結果

class Solution {
    fun isHappy(n: Int): Boolean {
        val seen = HashSet<Int>()
        var num = n
        while (num != 1 && num !in seen) {
            seen.add(num)
            num = getNext(num)
        }
        return num == 1
    }

    private fun getNext(n: Int): Int {
        var sum = 0
        var num = n
        while (num > 0) {
            val digit = num % 10
            sum += digit * digit
            num /= 10
        }
        return sum
    }
}

⭐2: Floyd 快慢指標#

概念: 慢指標每次算一步，快指標每次算兩步。若最終到 1 則是快樂數，若快慢相遇則有環
時間複雜度: O(log n)
空間複雜度: O(1) - 只用兩個指標

class Solution {
    fun isHappy(n: Int): Boolean {
        var slow = n
        var fast = getNext(n)
        while (fast != 1 && slow != fast) {
            slow = getNext(slow)
            fast = getNext(getNext(fast))
        }
        return fast == 1
    }

    private fun getNext(n: Int): Int {
        var sum = 0
        var num = n
        while (num > 0) {
            val digit = num % 10
            sum += digit * digit
            num /= 10
        }
        return sum
    }
}

補充：數學分析

對於 3 位數以下的數字，各位平方和最大為 9^2 * 3 = 243。因此所有數字最終都會收斂到 243 以下的循環。已知不快樂的數會進入以下循環：4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4。

可以直接硬編碼檢查：

class Solution {
    fun isHappy(n: Int): Boolean {
        val cycleMembers = setOf(4, 16, 37, 58, 89, 145, 42, 20)
        var num = n
        while (num != 1 && num !in cycleMembers) {
            num = getNext(num)
        }
        return num == 1
    }

    private fun getNext(n: Int): Int {
        var sum = 0
        var num = n
        while (num > 0) {
            val digit = num % 10
            sum += digit * digit
            num /= 10
        }
        return sum
    }
}

🔑 Takeaways#

Pattern: 將數學迭代問題轉化為「鏈結串列找環」問題
關鍵技巧: Floyd 快慢指標不只適用於鏈結串列，任何會產生循環的迭代過程都能用