來自：小浩算法
本題是leetcode第12題，意為整數(shù)轉(zhuǎn)羅馬數(shù)字，題目難度中等，代碼通過九萬次，建議掌握。
第12題：羅馬數(shù)字包含以下七種字符：I， V， X，L，C，D 和 M。
字符 數(shù)值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 羅馬數(shù)字 2 寫做 II ，即為兩個并列的 1。12 寫做 XII ，即為 X + II 。27 寫做 XXVII， 即為 XX + V + II 。
通常情況下，羅馬數(shù)字中小的數(shù)字在大的數(shù)字的右邊。但也存在特例，例如 4 不寫做 IIII，而是 IV。數(shù)字 1 在數(shù)字 5 的左邊，所表示的數(shù)等于大數(shù) 5 減小數(shù) 1 得到的數(shù)值 4 。同樣地，數(shù)字 9 表示為 IX。這個特殊的規(guī)則只適用于以下六種情況：
I 可以放在 V (5) 和 X (10) 的左邊，來表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左邊，來表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左邊，來表示 400 和 900。
給定一個整數(shù)，將其轉(zhuǎn)為羅馬數(shù)字。輸入確保在 1 到 3999 的范圍內(nèi)。
示例 1:
輸入: 3
輸出: "III"
示例 2:
輸入: 4
輸出: "IV"
示例 3:
輸入: 9
輸出: "IX"
示例 4:
輸入: 58
輸出: "LVIII"
解釋: L = 50, V = 5, III = 3.
示例 5:
輸入: 1994
輸出: "MCMXCIV"
解釋: M = 1000, CM = 900, XC = 90, IV = 4.
看見長長的題目，別慫。
因?yàn)轭}目很長，所以讀懂題意很重要。這道題說是讓我們轉(zhuǎn)換羅馬數(shù)字，其實(shí)說白了就是讓我們用特殊的規(guī)則湊數(shù)。羅馬數(shù)字本身就可以理解為一種特殊的數(shù)學(xué)規(guī)則。
那如何來湊數(shù)？自然就需要讀懂題意，比如 2 就是通過 1+1 湊；3 通過 1+1+1 湊；6 通過 5+1 湊。同時，在湊的過程中，又加入了一些奇怪的規(guī)則。比如說，4 不允許 1+1+1+1 湊，而是得 5-1 湊；而 9 不能 5+1+1+1+1 湊，而是得 10-1 湊；這個分析怎么出來的？題目中說的：
I 可以放在 V (5) 和 X (10) 的左邊，來表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左邊，來表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左邊，來表示 400 和 900。
看到這里，估計熟悉的小伙伴，能找到那么點(diǎn)感覺。湊數(shù)，湊數(shù)，湊錢。有一道很經(jīng)典的題目 “硬幣找零” 不也是一樣的玩法嗎。
然后，我們把題目中所有的字符列出來：
當(dāng)然，除了這些還不夠。因?yàn)樯厦嫖覀冞€分析出了一些特殊的規(guī)則，也得列出來：
然后我們利用這張表格，對給出的數(shù)字進(jìn)行轉(zhuǎn)化（拼湊）。假設(shè)我們要找的數(shù)為2834，大概的流程如下（其實(shí)是一種類似貪心的思想）：
對比著代碼看更為明朗：
1//java
2class Solution {
3 public String intToRoman(int num) {
4 int[] nums = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
5 String[] romans = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
6 int index = 0;
7 StringBuilder result = new StringBuilder();
8 while (index < 13) {
9 if (num >= nums[index]) {
10 result.append(romans[index]);
11 num -= nums[index];
12 } else {
13 index ++;
14 }
15 }
16 return result.toString();
17 }
18}
鄭重申明（讀我的文章必看）：
本系列所有教程都不會用到復(fù)雜的語言特性，大家無須擔(dān)心沒有學(xué)過相關(guān)語法，算法思想才是最重要的！
作為學(xué)術(shù)文章，雖然風(fēng)格可以風(fēng)趣，但嚴(yán)謹(jǐn)，我是認(rèn)真的。本文所有代碼均在leetcode進(jìn)行過測試運(yùn)行。
這道題目限制了最大數(shù)為 3999，時間復(fù)雜度也就被限制成了O(1)。
我還看到了一個西PP很騷的解法，拿出來大家瞅瞅：
1//cpp
2class Solution {
3public:
4 string intToRoman(int num)
5 {
6 char* c[4][10] = {
7 {"","I","II","III","IV","V","VI","VII","VIII","IX"},
8 {"","X","XX","XXX","XL","L","LX","LXX","LXXX","XC"},
9 {"","C","CC","CCC","CD","D","DC","DCC","DCCC","CM"},
10 {"","M","MM","MMM"}
11 };
12 string roman;
13 roman.append(c[3][num / 1000]);
14 roman.append(c[2][num / 100 % 10]);
15 roman.append(c[1][num / 10 % 10]);
16 roman.append(c[0][num % 10]);
17
18 return roman;
19 }
20};
這個解法應(yīng)該沒什么解釋的，就是把每一位 0-10 的情況枚舉出來。這道題目稍微長了點(diǎn)，但是分析下來并沒有什么難度。
長按訂閱更多精彩▼
如有收獲，點(diǎn)個在看，誠摯感謝
免責(zé)聲明：本文內(nèi)容由21ic獲得授權(quán)后發(fā)布，版權(quán)歸原作者所有，本平臺僅提供信息存儲服務(wù)。文章僅代表作者個人觀點(diǎn)，不代表本平臺立場，如有問題，請聯(lián)系我們，謝謝！
下載文檔
