每日一道 LeetCode (55)：整數(shù)轉(zhuǎn)羅馬數(shù)字
每天 3 分鐘，走上算法的逆襲之路。
前文合集
代碼倉庫
GitHub：https://github.com/meteor1993/LeetCode
Gitee：https://gitee.com/inwsy/LeetCode
題目：整數(shù)轉(zhuǎn)羅馬數(shù)字
難度：中等
題目來源：https://leetcode-cn.com/problems/integer-to-roman/
羅馬數(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.
解題思路
休息一段時間，我又回來做題了。
這道題難度不大，我估計把難度定成中等是因為大多數(shù)國人不大熟悉羅馬數(shù)字的轉(zhuǎn)化規(guī)則。
首先，羅馬數(shù)字是由 7 個單字母符號組成，每個符號都有自己的價值。減法規(guī)則給出了額外的 6 個符號。這就總共有 13 個獨特的符號。
M?->?1000
D?->?500
C?->?100
L?->?50
X?->?10
V?->?5
I?->?1
CM?->?900
CD?->?400
XC?->?90
XL?->?40
IX?->?9
IV?->?4
知道了上面這個對應(yīng)關(guān)系，還有一個問題需要了解，大一點的數(shù)字可能會有多種組成方式，那么哪種方式才是正確的？
比如，現(xiàn)在有一個數(shù)字 140 ，它可以表示的方式有很多種：
L?+?L?+?XL???????????=?50?+?50?+?40????????????=?140
C?+?X?+?X?+?X?+?X????=?100?+?10?+?10?+?10?+?10?=?140
C?+?XL???????????????=?100?+?40????????????????=?140
XC?+?L???????????????=?90?+?50?????????????????=?140
XL?+?XL?+?XL?+?X?+?X?=?40?+?40?+?40?+?10?+?10??=?140
上面這么多組合哪個是對的呢？
規(guī)則是從左向右，盡可能大的符號表示。
上面那就是 C 開頭的兩種方式：
C?+?X?+?X?+?X?+?X????=?100?+?10?+?10?+?10?+?10?=?140
C?+?XL???????????????=?100?+?40????????????????=?140
接著看第二個符號， XL（40） 當(dāng)然比 X（10） 更大，那么最終的結(jié)果就是 CXL 。
有了這些知識，這道題就已經(jīng)很簡單了，直接從左側(cè)開始，先尋找適合它的最大的符號，然后減去它，尋找剩余數(shù)字合適的最大的符號，接著依次取到最后，將得到的結(jié)果拼接起來，就是我們需要的結(jié)果：
public?class?Solution?{
????int[]?values?=?{1000,?900,?500,?400,?100,?90,?50,?40,?10,?9,?5,?4,?1};
????String[]?symbols?=?{"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
????public?String?intToRoman(int?num)?{
????????StringBuilder?sb?=?new?StringBuilder();
????????for?(int?i?=?0;?i?=?0;?i++)?{
????????????while?(values[i]?<=?num)?{
????????????????num?-=?values[i];
????????????????sb.append(symbols[i]);
????????????}
????????}
????????return?sb.toString();
????}
}
在答案上我看到了另一種更坑的解法，對每一位數(shù)字進(jìn)行硬編碼。
首先把數(shù)字分成千位、百位、十位、和個位，當(dāng)數(shù)字比 1000 大時，我們第一位加一個 M ，并從整數(shù)中減去 1000 ，接下來是的數(shù)字從 100 ~ 999 ，最高的符號是 CM(900)，最低的是 C(100) ，只要余數(shù)仍在 100 以上，我們就至少可以取 C(100) ，接下來同理是十位和個位。
因此，我們可以計算出每個數(shù)字在每個地方的表示形式。總共有 34 個，如下表：
代碼如下：
public?class?Solution1?{
????public?String?intToRoman(int?num)?{
????????String[]?thousands?=?{"",?"M",?"MM",?"MMM"};
????????String[]?hundreds?=?{"",?"C",?"CC",?"CCC",?"CD",?"D",?"DC",?"DCC",?"DCCC",?"CM"};
????????String[]?tens?=?{"",?"X",?"XX",?"XXX",?"XL",?"L",?"LX",?"LXX",?"LXXX",?"XC"};
????????String[]?ones?=?{"",?"I",?"II",?"III",?"IV",?"V",?"VI",?"VII",?"VIII",?"IX"};
????????return?thousands[num?/?1000]?+?hundreds[num?%?1000?/?100]?+?tens[num?%?100?/?10]?+?ones[num?%?10];
????}
}
這種方法我個人不推薦使用，完全就是窮舉法，把所有的可能全都窮舉出來。
