EP.22LeetCode 刷題日記

Math
數學解題技巧

#9 Palindrome Number · #50 Pow(x, n) · #202 Happy Number · #204 Count Primes — 快速冪、篩法、Floyd 判環，把數學性質變成演算法武器

Joseph Chen 2026 14 min read Fast Power · Sieve · Cycle Detection

「計算 2 的 100 次方。」

如果你用迴圈乘 100 次，沒有問題。但如果是 2 的 10 億次方呢？ 快速冪告訴我們：先算 2²=4，再算 4²=16，再算 16²=256…… 每次「平方」就把指數減半，只需要 log₂(n) 步。 這就是 Math 類題目的精髓——觀察數學規律，把 O(n) 壓縮成 O(log n) 甚至 O(1)。

#9

Palindrome Number

判斷一個整數是否是回文數，不能轉成字串

範例

121 → True

1
2
1

-121 → False

-
1
2
1

120 → False（結尾 0）

1
2
0

關鍵思路：只反轉後半段

不需要完整反轉整個數字。把後半段的數字逐位「撥進」 reversed_half， 直到 x <= reversed_half（代表後半段已處理完畢）。 最後比較前後兩半是否相等。

x = 1221 的過程

0x=1221rev=0初始
1x=122rev=1rev = 0*10 + 1%10 = 1，x = 1221//10 = 122
2x=12rev=12rev = 1*10 + 2 = 12，x = 12

x (12) == rev (12) → True ✓

Edge Case：先排除這兩種情況

  • 負數：x < 0 → False
  • 末尾為 0 且非 0：x % 10 == 0 and x != 0 → False（反轉後前面會有多餘的 0）

奇數位數（如 121）：迴圈結束時 x = 1，rev = 12， 比較 x == rev // 10 即可（忽略中間那位）。

⏱ Time: O(log n)💾 Space: O(1)
palindrome_number.py
def isPalindrome(x: int) -> bool:
    if x < 0 or (x % 10 == 0 and x != 0):
        return False

    reversed_half = 0
    while x > reversed_half:
        reversed_half = reversed_half * 10 + x % 10
        x //= 10

    # 偶數位：x == reversed_half
    # 奇數位：x == reversed_half // 10（忽略中間那位）
    return x == reversed_half or x == reversed_half // 10
#50

Pow(x, n)

實作 pow(x, n)，n 可能為負整數

Input: x = 2.0, n = 10 → Output: 1024.0

Input: x = 2.0, n = -2 → Output: 0.25

快速冪（Binary Exponentiation）

核心思路：每次把指數減半，底數自乘。

遞推公式

x^n = (x²)^(n/2)   若 n 為偶數

x^n = x · (x²)^((n-1)/2)   若 n 為奇數

x^0 = 1   基底

2^10 的計算過程

n=10x=2n 偶 → 2^10 = (2²)^5→4^5
n=5x=4n 奇 → 4^5 = 4 · (4²)^2→4 · 16^2
n=2x=16n 偶 → 16^2 = (16²)^1→256^1
n=1x=256n 奇 → 256^1 = 256 · (256²)^0→256 · 1 = 256

4 · 256 = 1024 ✓（回溯收集奇數位的餘數）

⏱ Time: O(log n)💾 Space: O(log n) 遞迴 / O(1) 迭代
pow_x_n.py
# 遞迴版（面試常考）
def myPow(x: float, n: int) -> float:
    if n == 0:
        return 1.0
    if n < 0:
        x, n = 1 / x, -n

    if n % 2 == 0:
        return myPow(x * x, n // 2)
    else:
        return x * myPow(x * x, n // 2)


# 迭代版（O(1) space，更優）
def myPow_iter(x: float, n: int) -> float:
    if n < 0:
        x, n = 1 / x, -n

    result = 1.0
    while n:
        if n & 1:          # n 為奇數：把目前的 x 乘進 result
            result *= x
        x *= x             # 底數平方
        n >>= 1            # 指數右移（除以 2）
    return result

迭代版的位元思維

把 n 看成二進位。例如 10 = 1010₂。從最低位開始，遇到 1 就把當前的 x 乘進 result， 然後底數平方。等效於 x^8 · x^2 = x^10， 因為 8+2=10，恰好對應二進位的 1 的位置。

#202

Happy Number

反覆對各位數字的平方和做替換，若最終到達 1 則是 happy number

Input: n = 19

19→1²+9²=82→8²+2²=68→6²+8²=100→1²+0²+0²=1

最終到達 1 → True（happy number）

核心問題：會無限循環嗎？

是的。不是 happy number 的數，一定會進入一個循環，永遠不會到達 1。 只要能偵測循環，就能判斷結果。

方法一：HashSet

把每次計算的結果存入 set。 若再次出現 → 進入循環 → False。 若出現 1 → True。

⏱ Time: O(log n)💾 Space: O(log n)

方法二：Floyd 判環（O(1) space）

同 Linked List Cycle 技巧：slow 走一步，fast 走兩步。 若 fast 到達 1 → True。 若 slow == fast（相遇）→ 進入循環 → False。

⏱ Time: O(log n)💾 Space: O(1)

Floyd 判環視覺化（n=4，非 happy）

0slow=4fast=4初始
1slow=16fast=37slow=next(4)=16，fast=next(next(4))=next(16)=37
2slow=37fast=58slow=next(16)=37，fast=next(37)=58
3slow=58fast=37slow=next(37)=58，fast=next(58)=89→next=145→next=42→next=20→next=4→next=16→next=37

slow == fast（循環）→ False

happy_number.py
def isHappy(n: int) -> bool:
    def get_next(num: int) -> int:
        total = 0
        while num:
            digit = num % 10
            total += digit * digit
            num //= 10
        return total

    # 方法一：HashSet
    seen = set()
    while n != 1:
        if n in seen:
            return False
        seen.add(n)
        n = get_next(n)
    return True


def isHappy_floyd(n: int) -> bool:
    def get_next(num: int) -> int:
        total = 0
        while num:
            digit = num % 10
            total += digit * digit
            num //= 10
        return total

    # 方法二：Floyd 判環（O(1) space）
    slow, fast = n, get_next(n)
    while fast != 1 and slow != fast:
        slow = get_next(slow)
        fast = get_next(get_next(fast))
    return fast == 1
#204

Count Primes

計算小於 n 的質數個數

Input: n = 10

小於 10 的質數：2, 3, 5, 7 → 共 4 個

Sieve of Eratosthenes（埃拉托斯特尼篩法）

建立布林陣列 is_prime[0..n-1]，初始全為 True。 從 2 開始，把每個質數的所有倍數標記為 False。 最後數一下還是 True 的個數。

n=20 的篩法過程

初始（2~19）

2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

篩掉 2 的倍數

2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

篩掉 3 的倍數

2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

篩掉 5 的倍數（5²=25>20，結束）

2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

剩餘質數：2,3,5,7,11,13,17,19 → 共 8 個（小於 20）

兩個關鍵優化

  • 外層迴圈只需到 √n（若 i > √n，i 的最小倍數 i² 已超過 n）
  • 內層從 i*i 開始標記，而非 2*i（2i 在處理 2 時已標記過了）
⏱ Time: O(n log log n)💾 Space: O(n)
count_primes.py
def countPrimes(n: int) -> int:
    if n < 2:
        return 0

    is_prime = [True] * n
    is_prime[0] = is_prime[1] = False

    i = 2
    while i * i < n:           # 只需到 √n
        if is_prime[i]:
            j = i * i          # 從 i² 開始，而非 2i
            while j < n:
                is_prime[j] = False
                j += i
        i += 1

    return sum(is_prime)

# 例：n=10 → 4（質數：2,3,5,7）

Math 解題技巧速查

技巧對應題型TimeSpace
反轉後半段數字#9 Palindrome NumberO(log n)O(1)
快速冪（迭代）#50 Pow(x, n)O(log n)O(1)
HashSet 判循環#202 Happy NumberO(log n)O(log n)
Floyd 判環#202 Happy NumberO(log n)O(1)
Sieve 篩法#204 Count PrimesO(n log log n)O(n)

本篇重點回顧

🪞Palindrome Number：只反轉後半段，用 x > reversed_half 當停止條件，O(1) 空間
⚡快速冪：n 奇數就乘進 result，n 偶數就底數平方，指數右移，O(log n) 解決 10 億次方
🔄Happy Number：不是 happy 一定進入循環；Floyd 判環比 HashSet 省空間（O(1) vs O(n)）
🧮Count Primes：篩法外層只到 √n，內層從 i² 開始，是最經典的空間換時間
💡Math 題通用策略：先找規律（奇偶/正負/邊界），再考慮能否用位移或平方壓縮複雜度

上一篇

EP.21 — Bit Manipulation

XOR、Brian Kernighan、Missing Number

下一篇

EP.23 — 即將推出

敬請期待

LeetCode
Math
Palindrome
Fast Power
Happy Number
Sieve
Python
EP.22