12 - Integer to Roman
Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.
Solution: 枚举，考虑每个字符以及每两个字符的组合
1 class Solution {
2 public:
3 string intToRoman(int num) { //runtime:28ms
4 string ret;
5 //M<-->1000
6 while(num >= 1000)
7 {
8 ret += 'M';
9 num -= 1000;
10 }
11 //to here, num < 1000
12 //CM<-->900
13 if(num >= 900)
14 {
15 ret += "CM";
16 num -= 900;
17 }
18 //to here, num < 900
19 //D<-->500
20 if(num >= 500)
21 {
22 ret += 'D';
23 num -= 500;
24 }
25 //to here, num < 500
26 if(num >= 400)
27 {
28 ret += "CD";
29 num -= 400;
30 }
31 //to here, num < 400
32 //C<-->100
33 while(num >= 100)
34 {
35 ret += 'C';
36 num -= 100;
37 }
38 //to here, num < 100
39 //XC<-->90
40 if(num >= 90)
41 {
42 ret += "XC";
43 num -= 90;
44 }
45 //to here, num < 90
46 //L<-->50
47 if(num >= 50)
48 {
49 ret += 'L';
50 num -= 50;
51 }
52 //to here, num < 50
53 //XL<-->40
54 if(num >= 40)
55 {
56 ret += "XL";
57 num -= 40;
58 }
59 //to here, num < 40
60 //X<-->10
61 while(num >= 10)
62 {
63 ret += 'X';
64 num -= 10;
65 }
66 //to here, num < 10
67 //IX<-->9
68 if(num >= 9)
69 {
70 ret += "IX";
71 num -= 9;
72 }
73 //to here, num < 9
74 //V<-->5
75 if(num >= 5)
76 {
77 ret += 'V';
78 num -= 5;
79 }
80 //to here, num < 5
81 //IV<-->4
82 if(num >= 4)
83 {
84 ret += "IV";
85 num -= 4;
86 }
87 //to here, num < 4
88 //I<-->1
89 while(num >= 1)
90 {
91 ret += 'I';
92 num -= 1;
93 }
94 return ret;
95 }
96 };
13 - Roman to Integer
Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.
Analysis：
| 基本字符 |
I
|
V
|
X
|
L
|
C
|
D
|
M
|
|---|---|---|---|---|---|---|---|
| 相应的阿拉伯数字表示为 |
1
|
5
|
10
|
50
|
100
|
500
|
1000
|
-
个位数举例Ⅰ－1、Ⅱ－2、Ⅲ－3、Ⅳ－4、Ⅴ－5、Ⅵ－6、Ⅶ－7、Ⅷ－8、Ⅸ－9
-
十位数举例Ⅹ－10、Ⅺ－11、Ⅻ－12、XIII－13、XIV－14、XV－15、XVI－16、XVII－17、XVIII－18、XIX－19、XX－20、XXI－21、XXII－22、XXIX－29、XXX－30、XXXIV－34、XXXV－35、XXXIX－39、XL－40、L－50、LI－51、LV－55、LX－60、LXV－65、LXXX－80、XC－90、XCIII－93、XCV－95、XCVIII－98、XCIX－99
-
百位数举例C－100、CC－200、CCC－300、CD－400、D－500、DC－600、DCC－700、DCCC－800、CM－900、CMXCIX－999
-
千位数举例M－1000、MC－1100、MCD－1400、MD－1500、MDC－1600、MDCLXVI－1666、MDCCCLXXXVIII－1888、MDCCCXCIX－1899、MCM－1900、MCMLXXVI－1976、MCMLXXXIV－1984、MCMXC－1990、MM－2000、MMMCMXCIX－3999
Solution 1: 借助map
1 class Solution { 2 public: 3 int romanToInt(string s) { //runtime:76ms 4 int ret=0; 5 map<char,int> m; 6 m['I']=1;m['V']=5;m['X']=10;m['L']=50;m['C']=100;m['D']=500;m['M']=1000; 7 for(int i=1;i<s.size();i++){ 8 if(m[s[i]]<=m[s[i-1]])ret+=m[s[i-1]]; 9 else 10 ret-=m[s[i-1]]; 11 } 12 ret+=m[s[s.size()-1]]; 13 return ret; 14 } 15 };
Solution 2: 每个字符前的字符确定，C前只可能是C或X，M前只可能是M或C
1 class Solution { 2 public: 3 int romanToInt(string s) { //runtime: 36ms 4 int n = 0; 5 char lastC = 0; 6 for(int i = 0; i < s.size(); i ++) 7 { 8 switch(s[i]) 9 { 10 case 'I': 11 n += 1; 12 lastC = s[i]; 13 break; 14 case 'V': 15 if(lastC == 'I') 16 {//IV 17 n -= 1; 18 n += 4; 19 lastC = 0; 20 } 21 else 22 { 23 n += 5; 24 lastC = s[i]; 25 } 26 break; 27 case 'X': 28 if(lastC == 'I') 29 {//IX 30 n -= 1; 31 n += 9; 32 lastC = 0; 33 } 34 else 35 { 36 n += 10; 37 lastC = s[i]; 38 } 39 break; 40 case 'L': 41 if(lastC == 'X') 42 {//XL 43 n -= 10; 44 n += 40; 45 lastC = 0; 46 } 47 else 48 { 49 n += 50; 50 lastC = s[i]; 51 } 52 break; 53 case 'C': 54 if(lastC == 'X') 55 {//XC 56 n -= 10; 57 n += 90; 58 lastC = 0; 59 } 60 else 61 { 62 n += 100; 63 lastC = s[i]; 64 } 65 break; 66 case 'D': 67 if(lastC == 'C') 68 {//CD 69 n -= 100; 70 n += 400; 71 lastC = 0; 72 } 73 else 74 { 75 n += 500; 76 lastC = s[i]; 77 } 78 break; 79 case 'M': 80 if(lastC == 'C') 81 {//CM 82 n -= 100; 83 n += 900; 84 lastC = 0; 85 } 86 else 87 { 88 n += 1000; 89 lastC = s[i]; 90 } 91 break; 92 default: 93 return 0; 94 } 95 } 96 return n; 97 } 98 };