Roman chart: http://literacy.kent.edu/Minigrants/Cinci/romanchart.htm
Integer to Roman
Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.
解析：只有数字为 9 和 4 时，取一个小数放在左边。（把数字为 9 和 4 时的罗马符号看作一个原子，避免取小数过程。）
1 class Solution { 2 public: 3 string intToRoman(int num) { 4 string Roman[13] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"}; 5 int val[13] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 }; 6 string s; 7 for(int i = 0; i < 13; ++i){ 8 while(num >= val[i]){ 9 num -= val[i]; 10 s += Roman[i]; 11 } 12 } 13 return s; 14 } 15 };
Roman to Integer
Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.
解析：1. 最直观想法，对字符串按罗马值从大到小比对。 (372 ms)
1 bool inHead(string s1, string& s2) 2 { 3 if(s2 == "") return false; 4 int k = 0; 5 auto it = s1.begin(); 6 for(; it != s1.end(); ++it) 7 { 8 if(*it != s2[k++]) return false; 9 } 10 if(it == s1.end()){ 11 s2.erase(0, k); 12 return true; 13 } 14 } 15 16 class Solution { 17 public: 18 int romanToInt(string s) { 19 string sigmal[13] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"}; 20 int a[13] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 }; 21 int num = 0; 22 int k = 0; 23 for(int i = 0; i < 13; ++i){ 24 while(inHead(sigmal[i], s)){ 25 num += a[i]; 26 } 27 } 28 return num; 29 } 30 };
2. 利用 hash 函数来做。(每个罗马字符范围都在 ‘A‘ - ‘Z‘ 之间，对字符串从左到右扫描，若是出现逆序（按罗马值），则这个逆序对为一个值) (260ms)
1 class Solution { 2 public: 3 int romanToInt(string s) { 4 char c[13] = {‘M‘, ‘D‘, ‘C‘, ‘L‘, ‘X‘, ‘V‘, ‘I‘}; 5 int v[13] = {1000, 500, 100, 50, 10, 5, 1 }; 6 int hash[256] = {0}; 7 for(int i = 0; i < 7; ++i){ 8 hash[c[i]] = v[i]; 9 } 10 int num = 0; 11 int len = s.length(); 12 for(int i = 0; i < len; ++i){ 13 if(i == len-1){ 14 num += hash[s[i]]; 15 return num; 16 } 17 if(hash[s[i]] < hash[s[i+1]]){ 18 num += hash[s[i+1]] - hash[s[i]]; 19 ++i; 20 }else num += hash[s[i]]; 21 } 22 return num; 23 } 24 };
5.Integer to Roman && Roman to Integer,布布扣,bubuko.com
5.Integer to Roman && Roman to Integer
原文：http://www.cnblogs.com/liyangguang1988/p/3691819.html
