Math 數學技巧 ·

介紹
#

數學題的套路比較分散，但常見的幾種想法是固定的：

想法	例子
不枚舉，直接數	相同的數有幾對、能切成幾種
逐位決定	第 `k` 個排列
幾何公式	最近點、餘弦定理、三角不等式
先觀察結構	排序後取固定位置、答案只跟頭尾有關

質數、GCD、篩法見 Number Theory。

模板一：組合計數
#

相同的東西兩兩配對：每種有 c 個，配對數是 c × (c - 1) / 2。邊掃邊數更簡單：

cnt = Counter()
pairs = 0
for x in items:
    pairs += cnt[x]                      # 跟前面每個相同的配一對
    cnt[x] += 1

相同數字的配對（LC 1512）。
凱薩密碼等價的字串（LC 3805）：先把每個字串正規化（整串平移到第一個字母是 a），等價的字串就變成一樣的，再數配對。

切成幾段：如果陣列必須切成 b 個不可再分的區塊，每個相鄰區塊之間可以切或不切，共 2^(b - 1) 種（LC 2963）。區塊用「每個數最後出現的位置」找，跟 LeetCode 2584 一樣。

模板二：第 k 個排列（逐位決定）
#

從左到右決定每一位：試每個可以放的字元，算「這一位放它之後，剩下的有幾種排法」，k 比這個數大就跳過（k 減掉它），否則就放它。

k -= 1                                   # 改成 0-indexed
digits = list(range(1, n + 1))
res = []
for i in range(n - 1, -1, -1):
    block = factorial(i)                 # 剩下 i 個數的排法
    idx, k = divmod(k, block)
    res.append(digits.pop(idx))

1..n 的第 k 個排列（LC 60）。
第 k 個回文排列（LC 3518）：回文由左半邊決定，變成「多重集合的第 k 個排列」。剩下的排法數是 total! / Π cnt!；放了字元 c 之後，排法數變成 目前排法數 × cnt[c] / 剩下的長度，可以 O(1) 更新。

模板三：幾何
#

圓和矩形有沒有重疊（LC 1401）：矩形裡離圓心最近的點，是把圓心座標 clamp 到矩形範圍內，再比較距離和半徑：

nx = min(max(xc, x1), x2)
ny = min(max(yc, y1), y2)
overlap = (nx - xc) ** 2 + (ny - yc) ** 2 <= r * r

三角形的內角（LC 3899）：先用三角不等式判斷能不能組成，再用餘弦定理 cos A = (b² + c² - a²) / 2bc。
矩形重疊（LC 836）：拆成 x、y 兩個區間，min(右) - max(左) > 0 兩個方向都成立才重疊。不要用「端點落在區間裡」分情況，會漏掉包含的情況。
三點的面積（LC 812）：鞋帶公式 |(x2 - x1)(y3 - y1) - (x3 - x1)(y2 - y1)| / 2。
最大周長的三角形（LC 976）：排序後，三條邊 a <= b <= c 能組成三角形 ⇔ a + b > c。從最大的開始看連續三個，第一個成立的就是答案。

模板四：先觀察結構
#

三等分的二進位值（LC 927）：三段的 1 的個數一定一樣，所以先數 1。第三段的結尾固定在陣列尾端（尾端的 0 都屬於它），由第三段決定每段的長度。
選三個數取中位數（LC 3627）：排序後，每次拿最大的兩個和最小的一個，中位數是第二大的；答案是從尾端往前每隔一個取。
最後剩下的數（LC 3828）：Alice 第一步就能刪掉除了頭或尾以外的全部，Bob 也一樣，答案是 max(頭, 尾)。
只有極值重要：每個數能調 ±k 時差距是 max(0, max - min - 2k)（LC 908）；三個數的最大乘積只可能是最大三個，或最小兩個乘最大一個（LC 628）；所有操作都包含左上角時，答案是交集 min(a) × min(b)（LC 598）。
移項讓每邊只跟一個 index 有關（LC 1814）：a[i] - rev(a[i]) == a[j] - rev(a[j])，就能用雜湊表數 pair。
博弈先看小的情況（LC 292）：面對 4 的倍數必輸。
感測器覆蓋（LC 3648）：每個感測器蓋 2k + 1 的寬度，兩個方向各自做無條件進位的除法再相乘。

模板五：位數與簡單公式
#

取出每一位：轉成字串最簡單；用 % 10、// 10 也可以，而且是從個位數開始：

digits = [int(c) for c in str(n)]        # 從最高位開始

while n:                                 # 從個位數開始
    d = n % 10
    n //= 10

位數和 / 積（LC 3550、1281、3622）、位數平方和（LC 3959：每一位的 d² - d >= 0，總和只會變大，達標就能提早回傳）。
兩個最大的位數相乘（LC 3536）、某個數字出現幾次（LC 3895、3908）。
拆成 d × 10^k 的和（LC 3697）：每個非 0 的位數就是一項。

直接套公式：min(n², maxWeight // w)（LC 3492）、攝氏轉換（LC 2469）、n 個和為 0 的不同整數（LC 1304：1..n/2 和它們的相反數，n 是奇數再加 0）、等差數列的 XOR（LC 1486）。

模板六：直式加法與乘法（進位）
#

數字用字串或陣列表示、不能直接轉成整數時，照直式從最低位開始算：

i, j, carry, res = len(a) - 1, len(b) - 1, 0, []
while i >= 0 or j >= 0 or carry:         # carry 放進條件，最後的進位不會漏
    x = int(a[i]) if i >= 0 else 0
    y = int(b[j]) if j >= 0 else 0
    carry, d = divmod(x + y + carry, 10)
    res.append(str(d))
    i, j = i - 1, j - 1
return "".join(reversed(res))

加一（LC 66）：從最後一位往前，不是 9 就加一回傳，是 9 就變 0；全部是 9 時前面補 1。
陣列加整數（LC 989）：把整個 k 當成進位，k += num[i]、取 k % 10、k //= 10。
字串相乘（LC 43）：a[i] * b[j] 加到 res[i + j + 1]，全部乘完再統一進位，最後去掉開頭的 0。

模板七：進位制轉換
#

digits = []
while n:
    n, r = divmod(n, base)
    digits.append(r)                     # 從最低位開始
digits.reverse()

七進位（LC 504）：對絕對值做，最後補負號；0 要特別處理。
Excel 欄名（LC 168、171）：每一位是 1..26，沒有 0，所以每一步用 divmod(n - 1, 26)。反方向是 res = res * 26 + 值。
反轉位數（LC 7、9）：rev = rev * 10 + n % 10。回文只要反轉後半段，直到 rev >= n。

模板八：快速冪
#

def power(x, n):
    res = 1
    while n:
        if n & 1:                        # 這一位是 1，乘進答案
            res *= x
        x *= x                           # x^(2^k)
        n >>= 1
    return res