12. Integer to Roman

題目 / Problem

中文： 給你一個整數 num，請將它轉換成羅馬數字並回傳對應的字串。

七個羅馬符號對應的數值：

轉換規則： - 從高位往低位依序處理每一個十進位位數。 - 一般情況下挑「能扣掉的最大值」對應符號附加上去，再扣除繼續處理。 - 若該位以 4 或 9 開頭，要用「減法形式」：4=IV、9=IX、40=XL、90=XC、400=CD、900=CM。 - I、X、C、M 最多連寫 3 次；V、L、D 不能連寫。

限制： 1 <= num <= 3999

English: Given an integer num (with 1 <= num <= 3999), convert it to a Roman numeral string. The seven Roman symbols I, V, X, L, C, D, M map to 1, 5, 10, 50, 100, 500, 1000 respectively. Numerals are built by processing decimal place values from highest to lowest, using the subtractive forms IV, IX, XL, XC, CD, CM whenever a place starts with 4 or 9. Powers of ten (I, X, C, M) may repeat at most three times in a row; V, L, D never repeat.

Worked example: num = 1994 → 1000 = M, 900 = CM, 90 = XC, 4 = IV → "MCMXCIV".

名詞解釋 / Glossary

• 羅馬數字 / Roman numeral — 一種古代記數系統，用 I、V、X、L、C、D、M 七個字母組合表示數字。An ancient numeral system using seven letters; numbers are built by adding (and occasionally subtracting) symbol values.
• 減法形式 / Subtractive form — 當某位是 4 或 9 時，用「較小符號放在較大符號左邊」表示相減（例如 IV=4、CM=900）。Six special two-letter pairs (IV, IX, XL, XC, CD, CM) where a smaller symbol before a larger one means "subtract."
• 貪心法 / Greedy algorithm — 每一步都挑當下能扣掉的最大數值，無需回溯。重複到剩 0 為止。At each step pick the largest value that fits; never reconsider. Works here because the Roman system is designed so this strategy is always optimal.
• 平行陣列 / Parallel arrays — 兩個長度相同的陣列，索引一一對應（一個放數值、一個放符號字串）。Two arrays of equal length where index i of each refers to the same logical item — used here to pair values with their Roman strings.
• 字串拼接 / String concatenation — 把多個字串接在一起。在 C 裡用 strcpy/手動複製字元；在 C++ 用 += 或 append。Joining strings end-to-end; in C we copy characters manually, in C++ we use +=.
• 時間複雜度 O(1) / Constant time — 不論輸入大小，操作次數都有固定上限。Here the input is bounded (num <= 3999) so the loop runs a bounded number of times.

思路

中文：最直觀的暴力做法是逐位（千、百、十、個）查表，每位各自寫一段 if/else 處理「是不是 4 或 9」、「要不要 V/L/D 加上幾個 I/X/C」。這樣能解，但要寫四段幾乎一樣的程式碼，又容易少打或打錯字母。觀察羅馬數字的設計：所有「會用到」的數值其實只有 13 個——七個基本符號 1, 5, 10, 50, 100, 500, 1000 加上六個減法形式 4, 9, 40, 90, 400, 900。如果把這 13 個數值從大到小排好，搭配對應的羅馬字串，就可以用「貪心法」：每次挑出當下能扣掉的最大值，把對應字串接到答案後面，再從 num 扣掉這個值，重複直到 num=0。為什麼貪心一定對？因為羅馬數字系統本身就是設計成「每一個十進位位數最多消耗一個減法形式 + 最多三個重複符號」，當我們把減法形式也視為一個原子單位放進候選清單，每個位都能在常數步內被消掉，不會出現「先選大的反而吃虧」的情況。關鍵不變式：迴圈每跑一輪，num 至少減少候選清單中當前最大可用值，因此一定會單調下降到 0。

English: The brute-force idea is to handle each decimal place (thousands, hundreds, tens, ones) with its own if/else chain that checks "is the digit 4 or 9, otherwise how many V/L/D plus I/X/C do I need?" It works but means writing four nearly identical blocks and is easy to typo. The cleaner observation is that the Roman system only ever needs 13 distinct values: the seven base symbols (1, 5, 10, 50, 100, 500, 1000) plus the six subtractive pairs (4, 9, 40, 90, 400, 900). List those 13 values from largest to smallest with their string forms and run a greedy loop: subtract the largest value that fits, append its string, repeat until num is 0. Greedy is provably correct here because Roman numerals are designed so each decimal place is consumed by at most one subtractive pair plus at most three repeats of a base symbol — treating the subtractive pairs as atomic candidates means we never have to backtrack. The loop invariant is that num strictly decreases on every iteration, so termination is guaranteed.

逐步走查 / Walkthrough

Trace with num = 3749. Candidate table (value → symbol), largest first: 1000→M, 900→CM, 500→D, 400→CD, 100→C, 90→XC, 50→L, 40→XL, 10→X, 9→IX, 5→V, 4→IV, 1→I.

迴圈在 num = 0 時結束，輸出 "MMMDCCXLIX"，與題目期望一致。Loop exits when num reaches 0, producing "MMMDCCXLIX" — matches the expected output.

Solution — C

// 演算法：把 13 個「值 → 羅馬符號」候選由大到小排好，每次扣掉能放的最大值並把符號接到答案後面。
// Algorithm: list 13 (value, symbol) candidates largest-first; greedily subtract the biggest
// value that fits into num and append its symbol to the answer until num reaches 0.

#include <stdlib.h>   // malloc / 動態配置記憶體 / for dynamic memory allocation
#include <string.h>   // strcpy / 字串複製 / for copying C-strings

char* intToRoman(int num) {
    // 平行陣列：values[i] 對應 symbols[i] / Parallel arrays: values[i] pairs with symbols[i].
    // 從大到小排好，這是貪心法的關鍵 / Sorted largest-first — required for the greedy loop.
    int values[13]      = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    const char* symbols[13] = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};

    // 最壞情況 3999 = MMMCMXCIX，長度 15；給 20 個字元的緩衝足夠且簡單 / Worst-case length
    // is 15 (for 3999); 20 bytes is a safe, simple upper bound including the '' terminator.
    char* result = (char*)malloc(20 * sizeof(char));
    // malloc 不會清零，先把第一個位元組設成 '' 形成空字串 / malloc doesn't zero memory,
    // so we set the first byte to '' to make result a valid empty C-string.
    result[0] = '';
    // len 追蹤目前已寫入的長度，避免每次都用 strlen 重新掃描 / len tracks current length so
    // we don't pay O(length) for strlen on every append.
    int len = 0;

    // 遍歷 13 個候選，從大到小 / Iterate through all 13 candidates, largest to smallest.
    for (int i = 0; i < 13; i++) {
        // 當前候選值還能扣就一直扣 / Subtract this value while it still fits — e.g. 3000
        // produces three 'M' appends before moving on.
        while (num >= values[i]) {
            // 把符號字串複製到 result 結尾 / Copy this symbol onto the end of result.
            // strcpy 會自動寫入結尾的 '' / strcpy also writes the trailing ''.
            strcpy(result + len, symbols[i]);
            // 更新長度：加上剛複製字串的長度 / Advance len by the length of the symbol we
            // just copied (1 for base symbols, 2 for subtractive pairs).
            len += (int)strlen(symbols[i]);
            // 從 num 扣掉這個值 / Subtract the value from num so the loop makes progress.
            num -= values[i];
        }
    }

    // LeetCode 會在使用後 free() 這塊記憶體，所以直接回傳即可 / LeetCode's harness frees
    // the returned pointer, so we just return it.
    return result;
}

Solution — C++

// 演算法：把 13 個「值 → 羅馬符號」候選由大到小排好，貪心地把最大可用值扣掉並接上符號。
// Algorithm: identical greedy strategy — walk a largest-first table of 13 (value, symbol)
// pairs, repeatedly subtracting the biggest value that fits while appending its symbol.

#include <string>   // std::string / C++ 的字串類別 / C++'s string class
#include <vector>   // std::vector / 動態陣列 / dynamic array container

class Solution {
public:
    std::string intToRoman(int num) {
        // const 表示這張表不會被修改 / const means we promise not to mutate the table.
        // std::vector<std::pair<int,std::string>>：每個元素是「整數值 + 對應符號」一組。
        // Each element pairs an int value with its Roman string; pair = two-element bundle.
        const std::vector<std::pair<int, std::string>> table = {
            {1000, "M"},  {900, "CM"}, {500, "D"},  {400, "CD"},
            {100,  "C"},  {90,  "XC"}, {50,  "L"},  {40,  "XL"},
            {10,   "X"},  {9,   "IX"}, {5,   "V"},  {4,   "IV"},
            {1,    "I"}
        };

        std::string result;       // 空字串開始，逐步拼接 / Start empty, append as we go.
        result.reserve(16);       // 預先配置最壞情況容量，避免多次重新配置 / Pre-allocate
                                  // capacity for the worst case (~15 chars) to avoid reallocs.

        // range-for + structured binding：直接把 pair 拆成 value 和 symbol 兩個變數。
        // C++17 structured binding: `auto& [a, b] = pair` unpacks the pair into two names.
        // 用 const auto& 避免複製 string / `const auto&` avoids copying the string each iter.
        for (const auto& [value, symbol] : table) {
            // 當前候選值還能扣就一直扣 / Keep subtracting this value while it still fits.
            while (num >= value) {
                result += symbol;  // string 的 += 直接把右邊接到尾端 / += appends in place.
                num -= value;      // 推進 num，保證迴圈會結束 / Decrease num to make progress.
            }
        }

        return result;  // RVO 會省略複製，回傳成本接近零 / Return value optimization avoids
                        // an extra copy here.
    }
};

複雜度 / Complexity

• Time: O(1) — 候選表固定有 13 個項目，且因為 num <= 3999，每個候選最多被使用 3 次（例如三個 M 表示 3000），所以總迭代次數有固定上限（最多約 15 次 append）。輸入大小有上界 → 常數時間。The candidate table has a fixed 13 entries, and because num is bounded by 3999, each entry is appended at most 3 times — total work is bounded by a constant (~15 appends).
• Space: O(1) — 輸出字串最長 15 字元（3999 → "MMMCMXCIX"），同樣有固定上界，不隨輸入規模增長。The output string is at most 15 characters (3999 → "MMMCMXCIX"); auxiliary memory is constant.

Pitfalls & Edge Cases

• 忘記減法形式 / Forgetting subtractive pairs — 如果只放七個基本符號就跑貪心，4 會變成 IIII、9 變成 VIIII，違反規則。把 4/9/40/90/400/900 也當作候選放進表裡，才會自然生成 IV/IX/...。Without listing the six subtractive pairs as candidates, greedy would output IIII for 4. Including them as atomic entries fixes this automatically.
• 候選順序錯了 / Table not sorted largest-first — 貪心法假設「先扣大的一定不會虧」。若順序錯亂，例如先放 100 再放 900，遇到 num=900 時會錯誤地接九個 C。一律從大到小排列就安全。Greedy correctness depends on descending order; mis-ordering breaks it (e.g. 900 would emit CCCCCCCCC).
• C 緩衝區太小 / C buffer too small — 用 malloc 配置時必須 ≥ 16（15 字元 + '\0'），否則 3999 會寫出界、產生未定義行為。20 是安全且簡單的選擇。The C buffer must hold 15 chars plus the null terminator; allocating less risks an overflow on the 3999 case.
• C 字串忘記 '\0' / Forgetting null terminator in C — malloc 不會清零，未先寫 '\0' 就 strcpy 到偏移位置會在前端讀到亂碼。先 result[0] = '\0' 才安全。malloc returns uninitialized memory; setting result[0] = '\0' first guarantees we start from a valid empty string.
• 改用 if 而非 while / Using if instead of while — 內層必須是 while，因為同一個值可能要扣多次（例如 3000 要扣三次 1000）。寫成 if 只會扣一次，結果會少符號。The inner loop must be while, not if — 3000 needs the 1000 entry consumed three times.