012 Integer to Roman[M]

1 題目描述

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

難度：Medium

2 題目樣例

無

3 題意分析

十進位數字轉羅馬數字。

所以這道題所有的難點就是搞清楚羅馬數字怎麼表達的咯？OK，掃一眼維基

也不算很麻煩（個鬼），但是實在不適合作一道演算法題吧，所以也難怪

4 思路分析

由於我實在是懶得手動實現這種題，所以下面兩道均摘自討論區。

1 偷懶法

題目已經限制了輸入，那不如就按照計數法把每一位對應出來。

class Solution { public: string intToRoman(int num) { static const string s[4][10]= { {"","I","II","III","IV","V","VI","VII","VIII","IX"}, {"","X","XX","XXX","XL","L","LX","LXX","LXXX","XC"}, {"","C","CC","CCC","CD","D","DC","DCC","DCCC","CM"}, {"","M","MM","MMM"}, }; return s[3][num/1000%10] + s[2][num/100%10] + s[1][num/10%10] + s[0][num%10]; } };

沒有什麼分析複雜度的意義，略去。

2 按位轉換

按照規則一點一點轉換即可。

class Solution {public: bool isMul(int n) { return (n + 1) % 5 == 0; } int getMult(const int & n) { if(n / 1000 > 0) return 1000; if(n / 100 > 0) return 100; if(n / 10 > 0) return 10; return 1; } string subProb(int &num) { map<int,string> val; val[1] = "I"; val[5] = "V"; val[10] = "X"; val[50] = "L"; val[100] = "C"; val[500] = "D"; val[1000] = "M"; int multiple = getMult(num); string ans = ""; int value = num / multiple; if(value == 4) ans += (val[multiple] + val[5 * multiple]), value -=4; else if(value == 9) ans += (val[multiple] + val[10 * multiple]), value -=9; else if(value >= 5) { ans += val[5 * multiple]; value -= 5; } for(int i = 0; i < value; i ++) ans += val[multiple]; num %= multiple; return ans; } string intToRoman(int num) { string ans = ""; while(num > 0) ans += subProb(num); return ans; }}

實現稍微複雜了點，不過這道題想考的估計也就是這些了吧。

如果把map的插入移到函數外面，整體時間複雜度 ，空間複雜度 。

5 後記

垃圾題（逃

推薦閱讀：