判斷一個數字
n是否為「快樂數」。快樂數的定義：反覆將數字替換為其各位數字的平方和，最終會得到 1。如果進入無限循環且不會到達 1，則不是快樂數。
Example:
Input: n = 19 Output: true (1^2 + 9^2 = 82 -> 8^2 + 2^2 = 68 -> … -> 1)
Intuition
TIP
核心思路：這是一個鏈結串列找環問題——用快慢指標檢測是否會進入循環。
- 反覆計算各位數字平方和，結果要嘛收斂到 1，要嘛進入循環
- 用 HashSet 記錄看過的數字可以偵測循環，但需要 O(n) 空間
- Floyd 快慢指標法：慢指標算一次、快指標算兩次，若相遇則有環
Approaches
1. HashSet Cycle Detection — O(log n) / O(log n)
- Idea: 用 Set 記錄每次計算的結果，如果出現重複表示進入循環
- Time:
O(log n)- 數字會快速縮小 - Space:
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's Fast & Slow Pointers — O(log n) / O(1)
- Idea: 慢指標每次算一步，快指標每次算兩步。若最終到 1 則是快樂數，若快慢相遇則有環
- Time:
O(log n) - Space:
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
}
}Note: Math Analysis
對於 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: 將數學迭代問題轉化為「鏈結串列找環」問題
- Key trick: Floyd 快慢指標不只適用於鏈結串列，任何會產生循環的迭代過程都能用