5.Integer to Roman && Roman to Integer

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 时的罗马符号看作一个原子，避免取小数过程。）

 class Solution {

 public:

     string intToRoman(int num) {

         string Roman[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

         int val[] = {, , , , , , , , , , , ,  };

         string s;

         for(int i = ; i < ; ++i){

             while(num >= val[i]){

                 num -= val[i];

                 s += Roman[i];

             }

         }

         return s;

     }

 };

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)

 bool inHead(string s1, string& s2)

 {

     if(s2 == "") return false;

     int k = ;

     auto it = s1.begin();

     for(; it != s1.end(); ++it)

     {

         if(*it != s2[k++]) return false;

     }

     if(it == s1.end()){

         s2.erase(, k);

         return true;

     }

 }

 class Solution {

 public:

     int romanToInt(string s) {

         string sigmal[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

         int a[] = {, , , , , , , , , , , ,  };

         int num = ;

         int k = ;

         for(int i = ; i < ; ++i){

             while(inHead(sigmal[i], s)){

                 num += a[i];

             }

         }

         return num;

     }

 };

Code

2. 利用 hash 函数来做。(每个罗马字符范围都在 'A' - 'Z' 之间，对字符串从左到右扫描，若是出现逆序（按罗马值），则这个逆序对为一个值) (260ms)

 class Solution {

 public:

     int romanToInt(string s) {

         char c[] = {'M', 'D', 'C', 'L', 'X', 'V', 'I'};

         int v[] = {, , , , , ,  };

         int hash[] = {};

         for(int i = ; i < ; ++i){

             hash[c[i]] = v[i];

         }

         int num = ;

         int len = s.length();

         for(int i = ; i < len; ++i){

             if(i == len-){

                 num += hash[s[i]];

                 return num;

             }

             if(hash[s[i]] < hash[s[i+]]){

                 num += hash[s[i+]] - hash[s[i]];

                 ++i;

             }else num += hash[s[i]];

         }

         return num;

     }

 };

巴特西

5.Integer to Roman && Roman to Integer

最新文章

热门文章