Description
tags: Math, String
Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
* Example 1:
*
*
* Input: 3
* Output: "III"
*
* Example 2:
*
*
* Input: 4
* Output: "IV"
*
* Example 3:
*
*
* Input: 9
* Output: "IX"
*
* Example 4:
*
*
* Input: 58
* Output: "LVIII"
* Explanation: L = 50, V = 5, III = 3.
*
*
* Example 5:
*
*
* Input: 1994
* Output: "MCMXCIV"
* Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
Solution
class Solution {
public:
string intToRoman(int num) {
// 1 <= num <= 3999
string res;
string roman[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
int digit[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
for (int i=0; num != 0; i++) {
while (num >= digit[i]) {
res += roman[i];
num -= digit[i];
}
}
return res;
}
};
Analysis
- Time complexity: O(m)
- Space complexity: O(m)
m is the number of bits.
Points
- 數(shù)字位數(shù)的處理： 以往處理一個數(shù)每位脂凶，總是先去計算位數(shù)慌洪，通過繁雜的取余和除去拿到每一位的數(shù)腮猖。這個solution中用了巧妙的轉(zhuǎn)換，化解了這個問題。注意這個for循環(huán)任内。當不方便從num入手取每一位時赋焕，轉(zhuǎn)換為從和num的每一位比較的標準數(shù)入手的方式。
- 也不需要用到map等勾哩，處理得很簡潔。采用一個string數(shù)組和一個int數(shù)組举哟，index相互對應思劳。
