漫畫：臭長(zhǎng)臭長(zhǎng)的高頻貪心面試題
來(lái)自：小浩算法
本題是leetcode第12題，意為整數(shù)轉(zhuǎn)羅馬數(shù)字，題目難度中等，代碼通過(guò)九萬(wàn)次，建議掌握。
第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 ，即為兩個(gè)并列的 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。這個(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.
看見(jiàn)長(zhǎng)長(zhǎng)的題目，別慫。
因?yàn)轭}目很長(zhǎng)，所以讀懂題意很重要。這道題說(shuō)是讓我們轉(zhuǎn)換羅馬數(shù)字，其實(shí)說(shuō)白了就是讓我們用特殊的規(guī)則湊數(shù)。羅馬數(shù)字本身就可以理解為一種特殊的數(shù)學(xué)規(guī)則。
那如何來(lái)湊數(shù)？自然就需要讀懂題意，比如 2 就是通過(guò) 1+1 湊；3 通過(guò) 1+1+1 湊；6 通過(guò) 5+1 湊。同時(shí)，在湊的過(guò)程中，又加入了一些奇怪的規(guī)則。比如說(shuō)，4 不允許 1+1+1+1 湊，而是得 5-1 湊；而 9 不能 5+1+1+1+1 湊，而是得 10-1 湊；這個(gè)分析怎么出來(lái)的？題目中說(shuō)的：
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。
看到這里，估計(jì)熟悉的小伙伴，能找到那么點(diǎn)感覺(jué)。湊數(shù)，湊數(shù)，湊錢。有一道很經(jīng)典的題目 “硬幣找零” 不也是一樣的玩法嗎。
然后，我們把題目中所有的字符列出來(lái)：
當(dāng)然，除了這些還不夠。因?yàn)樯厦嫖覀冞€分析出了一些特殊的規(guī)則，也得列出來(lái)：
然后我們利用這張表格，對(duì)給出的數(shù)字進(jìn)行轉(zhuǎn)化（拼湊）。假設(shè)我們要找的數(shù)為2834，大概的流程如下（其實(shí)是一種類似貪心的思想）：
對(duì)比著代碼看更為明朗：
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}
鄭重申明（讀我的文章必看）：
本系列所有教程都不會(huì)用到復(fù)雜的語(yǔ)言特性，大家無(wú)須擔(dān)心沒(méi)有學(xué)過(guò)相關(guān)語(yǔ)法，算法思想才是最重要的！
作為學(xué)術(shù)文章，雖然風(fēng)格可以風(fēng)趣，但嚴(yán)謹(jǐn)，我是認(rèn)真的。本文所有代碼均在leetcode進(jìn)行過(guò)測(cè)試運(yùn)行。
這道題目限制了最大數(shù)為 3999，時(shí)間復(fù)雜度也就被限制成了O(1)。
我還看到了一個(gè)西PP很騷的解法，拿出來(lái)大家瞅瞅：
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};
這個(gè)解法應(yīng)該沒(méi)什么解釋的，就是把每一位 0-10 的情況枚舉出來(lái)。這道題目稍微長(zhǎng)了點(diǎn)，但是分析下來(lái)并沒(méi)有什么難度。
長(zhǎng)按訂閱更多精彩▼
如有收獲，點(diǎn)個(gè)在看，誠(chéng)摯感謝
免責(zé)聲明：本文內(nèi)容由21ic獲得授權(quán)后發(fā)布，版權(quán)歸原作者所有，本平臺(tái)僅提供信息存儲(chǔ)服務(wù)。文章僅代表作者個(gè)人觀點(diǎn)，不代表本平臺(tái)立場(chǎng)，如有問(wèn)題，請(qǐng)聯(lián)系我們，謝謝！
下載文檔
