點(diǎn)擊 這里 可以查看更多算法面試相關(guān)內(nèi)容~
題目描述
羅馬數(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 寫(xiě)做 II ，即為兩個(gè)并列的 1磺浙。12 寫(xiě)做 XII 洪囤，即為 X + II 。 27 寫(xiě)做 XXVII, 即為 XX + V + II 撕氧。
通常情況下瘤缩，羅馬數(shù)字中小的數(shù)字在大的數(shù)字的右邊。但也存在特例伦泥，例如 4 不寫(xiě)做 IIII剥啤，而是 IV。數(shù)字 1 在數(shù)字 5 的左邊不脯，所表示的數(shù)等于大數(shù) 5 減小數(shù) 1 得到的數(shù)值 4 府怯。同樣地，數(shù)字 9 表示為 IX防楷。這個(gè)特殊的規(guī)則只適用于以下六種情況：
- I 可以放在 V (5) 和 X (10) 的左邊牺丙，來(lái)表示 4 和 9。
- X 可以放在 L (50) 和 C (100) 的左邊复局，來(lái)表示 40 和 90冲簿。
- C 可以放在 D (500) 和 M (1000) 的左邊，來(lái)表示 400 和 900亿昏。
給定一個(gè)整數(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.
貪心解法
根據(jù)題意，我們可以列舉出有限個(gè)羅馬字符和其對(duì)應(yīng)的數(shù)值。
然后從左到右構(gòu)建羅馬數(shù)字彤断，優(yōu)先構(gòu)建數(shù)值高的羅馬字符（如果有足夠的分值野舶，盡量嘗試構(gòu)建 "M"，直到分值不夠宰衙，再盡量嘗試構(gòu)建 "CM" ... ）：
class Solution {
int[] val = new int[]{1000,900,500,400,100,90,50,40,10,9,5,4,1};
String[] str = new String[]{"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
public String intToRoman(int x) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < val.length && x > 0; i++) {
int cv = val[i];
String cs = str[i];
while (x >= cv) {
sb.append(cs);
x -= cv;
}
}
return sb.toString();
}
}
時(shí)間復(fù)雜度：計(jì)算量與最終羅馬數(shù)字的長(zhǎng)度成正比平道。對(duì)于每一位阿拉伯?dāng)?shù)字，羅馬數(shù)字最多用 4 個(gè)字母表示（比如 VIII = 8）供炼，所以羅馬數(shù)字的長(zhǎng)度最多不超過(guò)阿拉伯?dāng)?shù)字長(zhǎng)度的 4 倍（同一數(shù)量級(jí)內(nèi)）一屋。阿拉伯?dāng)?shù)字的長(zhǎng)度約為 logN，因此羅馬數(shù)字的長(zhǎng)度不超過(guò) 4 * logN袋哼。復(fù)雜度為 O(logn)（別忘了復(fù)雜度是忽略常數(shù)的）
空間復(fù)雜度：雖然使用了兩個(gè)數(shù)組記錄羅馬字符和數(shù)值冀墨，但消耗的空間固定，不隨著樣本大小而變化涛贯。復(fù)雜度為 O(1)
最后
這是我們「刷穿 LeetCode」系列文章的第 No.12 篇诽嘉，系列開(kāi)始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目弟翘，部分是有鎖題虫腋，我們將先將所有不帶鎖的題目刷完。
在這個(gè)系列文章里面稀余，除了講解解題思路以外悦冀，還會(huì)盡可能給出最為簡(jiǎn)潔的代碼。如果涉及通解還會(huì)相應(yīng)的代碼模板睛琳。
由于 LeetCode 的題目隨著周賽 & 雙周賽不斷增加盒蟆，為了方便我們統(tǒng)計(jì)進(jìn)度，我們將按照系列起始時(shí)的總題數(shù)作為分母掸掏，完成的題目作為分子茁影，進(jìn)行進(jìn)度計(jì)算。當(dāng)前進(jìn)度為 12/1916 丧凤。
為了方便各位同學(xué)能夠電腦上進(jìn)行調(diào)試和提交代碼募闲，我建立了相關(guān)的倉(cāng)庫(kù)：Github 地址 & Gitee 地址。
在倉(cāng)庫(kù)地址里愿待，你可以看到系列文章的題解鏈接浩螺、系列文章的相應(yīng)代碼、LeetCode 原題鏈接和一些其他的優(yōu)選題解仍侥。
</br>
