[LeetCode] 學會轉羅馬數字，你也會轉古埃及數字 #12 Integer to Roman
古埃及數字轉法
我們先來看古埃及數字轉法，3942 我們就一位數一位數慢慢轉:
每次遇到 9 大概就是最麻煩的時候，竟然要寫 9 次！
因為古埃及數字系統裡面就沒有用一個符號代表 9 的圖案，只好乖乖寫囉。
中文數字轉法
我們再來看一個應該非常熟悉的語言:
至少這比古埃及來的簡單: "九百" 代表 900, "八百" 代表 800... 這樣至少寫的字就少一點了。
羅馬數字轉法
那我們再來看看羅馬數字系統，就會發現它其實混合了上面兩種方式:
查表法
如果我們去看一下羅馬數字的 Wikipedia 網頁，我們會看到這樣的 table:
| Thousands | Hundreds | Tens | Units | |
|---|---|---|---|---|
| 1 | M | C | X | I |
| 2 | MM | CC | XX | II |
| 3 | MMM | CCC | XXX | III |
| 4 | CD | XL | IV | |
| 5 | D | L | V | |
| 6 | DC | LX | VI | |
| 7 | DCC | LXX | VII | |
| 8 | DCCC | LXXX | VIII | |
| 9 | CM | XC | IX |
所以我們就先找出每個十進位的數字: 3492 = 3, 4, 9, 2 再來轉成羅馬數字的 string:
class Solution {
public:
std::string intToRoman(int num) {
const int digit1000 = ((num % 10000) / 1000);
const int digit100 = ((num % 1000) / 100);
const int digit10 = ((num % 100) / 10);
const int digit1 = ((num % 10) / 1);
return digitToRoman1000(digit1000) + digitToRoman100(digit100) +
digitToRoman10(digit10) + digitToRoman1(digit1);
}
std::string digitToRoman1000(const int digit) {
static const char *TABLE[] = {"", "M", "MM", "MMM", "",
"", "", "", "", ""};
return TABLE[digit];
}
std::string digitToRoman100(const int digit) {
static const char *TABLE[] = {"", "C", "CC", "CCC", "CD",
"D", "DC", "DCC", "DCCC", "CM"};
return TABLE[digit];
}
std::string digitToRoman10(const int digit) {
static const char *TABLE[] = {"", "X", "XX", "XXX", "XL",
"L", "LX", "LXX", "LXXX", "XC"};
return TABLE[digit];
}
std::string digitToRoman1(const int digit) {
static const char *TABLE[] = {"", "I", "II", "III", "IV",
"V", "VI", "VII", "VIII", "IX"};
return TABLE[digit];
}
};
重複字串的做法
羅馬數字有時候可以重複數字，像是 3 = III，有時候又不行，像是 9 = IV 而不是 IIIIIIIII。
所以如果你又想要用 for loop 重複數字，又想要查表的話，舉棋不定的結果通常就是寫出有 bug 的程式。
我們設計演算法就是要越簡單越好，概念最好也只有一個，不要兩三個。
如果我們要重複，我們就要更細的把它拆開:
3678 = 3000 + 600 + 70 + 8
= 3000 + (500 + 100) + (50 + 20) + (5 + 3)
= 3*1000 + (500 + 1*100) + (50 + 2*10) + (5 + 3*1)
= 3*M + (D + 1*C) + (L + 2*X) + (V + 3*I)
= MMM.DC.LXX.VIII
這樣的過程我們就可以寫出很蠢但是很直覺的程式:
class Solution {
public:
std::string intToRoman(int num) {
std::string roman;
while (num >= 1000) {
roman += "M";
num -= 1000;
}
while (num >= 900) {
roman += "CM";
num -= 900;
}
while (num >= 500) {
roman += "D";
num -= 500;
}
while (num >= 400) {
roman += "CD";
num -= 400;
}
while (num >= 100) {
roman += "C";
num -= 100;
}
while (num >= 90) {
roman += "XC";
num -= 90;
}
while (num >= 50) {
roman += "L";
num -= 50;
}
while (num >= 40) {
roman += "XL";
num -= 40;
}
while (num >= 10) {
roman += "X";
num -= 10;
}
while (num >= 9) {
roman += "IX";
num -= 9;
}
while (num >= 5) {
roman += "V";
num -= 5;
}
while (num >= 4) {
roman += "IV";
num -= 4;
}
while (num >= 1) {
roman += "I";
num -= 1;
}
return roman;
}
};
然後我們再把上面這段程式碼 refactor 一下就可以變成這樣:
struct RomanAndValue {
std::string romanStr;
int value = 0;
};
class Solution {
public:
std::string intToRoman(int num) {
static const RomanAndValue TABLE[] = {
{"M", 1000}, {"CM", 900}, {"D", 500}, {"CD", 400}, {"C", 100},
{"XC", 90}, {"L", 50}, {"XL", 40}, {"X", 10}, {"IX", 9},
{"V", 5}, {"IV", 4}, {"I", 1},
};
std::string roman;
for (const auto &item : TABLE) {
while (num >= item.value) {
roman += item.romanStr;
num -= item.value;
}
}
return roman;
}
};
當然你也可以用 2 個 arrays、vector + pair 等方式來達成，只是我這邊用 struct 就是講清楚說明白我想要存取哪一個 member。
Submission 結果
這題就沒什麼好爭速度的:
你甚至可以寫 3999 行的程式碼直接回傳 1~3999 對應的羅馬數字，O(1) 鐵定爆快。
結語
看了 Wikipedia 才知道羅馬數字在中世紀的用法是很混亂的，甚至還有 4 = "IIII" 這種變形存在，所以拿來當題目大概就是要考驗你能不能在混亂中找出一些規律?
小心了如果面試問了這題，進公司後是不是就要在混亂中求生存?
下一篇我們用超懶惰的方法把羅馬數字轉回阿拉伯數字。
留言
發佈留言