高效構造範圍內所有回文數：按長度生成避免遍歷檢查

算法思路

回文數對稱，由前半部分決定。按位數長度分類生成：

• 奇數長度：前半段 + 中間位 + 前半段逆序。如 12321 由 12 + 3 + 21 構成。
• 偶數長度：前半段 + 前半段逆序。如 1221 由 12 + 21 構成。

生成代碼框架

// 1 位數
for (int i = 1; i < 10; i++) output(i);

// 2 位數
for (int i = 1; i < 10; i++) output(i * 10 + i);

// 3 位數
for (int i = 10; i < 100; i++) output(i * 100 + reverse(i / 10));

// 4 位數
for (int i = 10; i < 100; i++) output(i * 100 + reverse(i));

// 5 位數
for (int i = 100; i < 1000; i++) output(i * 100 + reverse(i / 10));

// 6 位數
for (int i = 100; i < 1000; i++) output(i * 1000 + reverse(i));
// ... 以此類推

輔助函數

int reverse(int x) {
    int r = 0;
    while (x > 0) { r = r * 10 + x % 10; x /= 10; }
    return r;
}

優勢

• 時間複雜度 O(√N) 生成 N 以內所有回文數，遠優於 O(N) 遍歷檢查。
• 天然有序生成，無需排序。
• 易於擴展到任意大範圍（如 10^12）。

掌握回文數構造模式，解決相關數論問題得心應手。