LeetCode 筆記：Integer to Roman 整數轉羅馬數字

題目描述

給定一個範圍在 1 到 3999 之間的整數，將其轉換為羅馬數字表示。羅馬數字規則：

• 基本符號：I=1, V=5, X=10, L=50, C=100, D=500, M=1000。
• 減法規則：IV=4, IX=9, XL=40, XC=90, CD=400, CM=900。

解題思路：貪心 + 查表

將所有可能的「值-符號」對按值從大到小排序：

int value[] = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
string symbol[] = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};

從最大值開始，只要 num >= value[i]，就將對應符號加入結果，並 num -= value[i]，重複直到 num == 0。這本質上是貪心策略，因為羅馬數字系統保證了這樣的拆分唯一且最優。

參考代碼

class Solution {
public:
    string intToRoman(int num) {
        string res;
        vector val = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
        vector sym = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
        for (int i = 0; num > 0; ++i) {
            while (num >= val[i]) {
                num -= val[i];
                res += sym[i];
            }
        }
        return res;
    }
};

複雜度

時間 O(1)（符號表固定長度 13），空間 O(1)。