Massive Algorithms: Integer and Roman Numeral

Integer and Roman Numeral | N00tc0d3r
Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.

Here is the wiki to introduce roman numeral symbols and their corresponding values.

Basic symbols are M, D, C, L, X, V, and I, representing 1000, 500, 100, 50, 10, 5 and 1.
But there are several special rules for 900, 400, 90, 40, 9 and 4 (see wiki for details).

https://leetcode.com/discuss/49870/my-java-solution-easy-to-understand
int[] values = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
String[] strs = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};

StringBuilder sb = new StringBuilder();

for(int i=0;i<values.length;i++) {
while(num >= values[i]) {
num -= values[i];
sb.append(strs[i]);
}
}
return sb.toString();
}
https://leetcode.com/discuss/62819/easy-to-understand-java-solution
public enum Type{ M(1000),CM(900),D(500),CD(400),C(100),XC(90),L(50),XL(40),X(10),IX(9),V(5),IV(4),I(1); private final int value; Type(int value) { this.value = value; } }; public String intToRoman(int num) { StringBuilder output = new StringBuilder(); for (Type t:Type.values()) { while (num>=t.value) { output.append(t); num -= t.value; } } return output.toString(); }

public String intToRoman(int num) {
int[] nums = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
StringBuilder res = new StringBuilder();
int i=0;
while (num>0) {
int times = num / nums[i];
num -= nums[i]*times;
for (; times>0; times--) {
res.append(symbols[i]);
}
++i;
}
return res.toString();
}
Roman to Integer
Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.
Solution

This is the reverse problem of the above one. And we need to consider the special cases when mapping roman numerals back to integer. So, in those cases, we need to check the successor char.
I:
/* int: 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1
* roman: "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"
*/
public int romanToInt(String s) {
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
map.put('M', 1000);
map.put('D', 500);
map.put('C', 100);
map.put('L', 50);
map.put('X', 10);
map.put('V', 5);
map.put('I', 1);

int res = 0, i = 0;
while (i<s.length()) {
switch(s.charAt(i)) {
case 'C':
case 'X':
case 'I':
if (i+1 < s.length()
&& map.get(s.charAt(i+1)) > map.get(s.charAt(i))) {
res += (map.get(s.charAt(i+1)) - map.get(s.charAt(i)));
i += 2;
} else {
res += map.get(s.charAt(i));
++i;
}
break;
default:
res += map.get(s.charAt(i));
++i;
}
}
return res;
}
II:
Or without using switch
/* int: 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1
* roman: "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"
*/
public int romanToInt(String s) {
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
map.put('M', 1000);
map.put('D', 500);
map.put('C', 100);
map.put('L', 50);
map.put('X', 10);
map.put('V', 5);
map.put('I', 1);

int res = 0;
for (int i=0; i<s.length(); ++i) {
char c = s.charAt(i);
if ((c == 'C' || c == 'X' || c == 'I')
&& i+1 < s.length() && map.get(s.charAt(i+1)) > map.get(c)) {
res += map.get(s.charAt(i+1)) - map.get(c);
++i;
} else {
res += map.get(c);
}
}
return res;
}
https://stupidcodergoodluck.wordpress.com/2014/03/31/leetcode-integer-to-roman/
其实就是那么几个符号，然后规律就是1,4,5,9,10然后每次十倍循环。算法就是给一个数，大于1000的时候就写上一个M, 还大于1000，再写一个M… 终于小于1000了，看看大于900不？，大于500不…如此类推。

        String[] symbols = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
        int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        StringBuilder ret = new StringBuilder();
        for (int i=0; i<values.length; i++) {
            while (num >= values[i]) {
                ret.append(symbols[i]);
                num -= values[i];
            }
        }
        return new String(ret);
    }

http://www.acmerblog.com/leetcode-solution-integer-to-roman-6231.html
Recursive Version:

02    public String intToRoman(int num) {

03        if(num>=1000) return "M"+intToRoman(num-1000);

04        if(num>=900) return "CM"+intToRoman(num-900);

05        if(num>=500) return "D"+intToRoman(num-500);

06        if(num>=400) return "CD"+intToRoman(num-400);

07        if(num>=100) return "C"+intToRoman(num-100);

08        if(num>=90) return "XC"+intToRoman(num-90);

09        if(num>=50) return "L"+intToRoman(num-50);

10        if(num>=40) return "XL"+intToRoman(num-40);

11        if(num>=10) return "X"+intToRoman(num-10);

12        if(num>=9) return "IX"+intToRoman(num-9);

13        if(num>=5) return "V"+intToRoman(num-5);

14        if(num>=4) return "IV"+intToRoman(num-4);

15        if(num>=1) return "I"+intToRoman(num-1);

16        return "";

17    }

05    string intToRoman(int num) {

06        const int radix[] = {1000, 900, 500, 400, 100, 90,

07                50, 40, 10, 9, 5, 4, 1};

08        const string symbol[] = {"M", "CM", "D", "CD", "C", "XC",

09                "L", "XL", "X", "IX", "V", "IV", "I"};

10

11        string roman;

12        for (size_t i = 0; num > 0; ++i) {

13            int count = num / radix[i];

14            num %= radix[i];

15            for (; count > 0; --count) roman += symbol[i];

16        }

17        return roman;

18    }

http://codesam.blogspot.com/2011/06/convert-integers-to-roman-numbers.html

string int2RomanNum(int intVal)
{
   if (intVal <= 0)
   {
      cout << "Roman numbers don't support 0 or negative! Return NULL" << endl;
      return ""; 
   }

   //build hash table of unique values 
   map valueMap;

   valueMap[1] = "I";
   valueMap[4] = "IV";
   valueMap[5] = "V";
   valueMap[9] = "IX";
   valueMap[10] = "X";
   valueMap[40] = "XL";
   valueMap[50] = "L";
   valueMap[90] = "XC";
   valueMap[100] = "C";
   valueMap[400] = "CD";
   valueMap[500] = "D";
   valueMap[900] = "CM";
   valueMap[1000] = "M";

   //the roman value
   string romanResult = "";

   //traverse the list in reverse order 
   map::reverse_iterator it;
   
   for (it = valueMap.rbegin(); it != valueMap.rend(); it++)
   {
      //if current number is greater than current key in list
      //add the value corresponded with key to result
      //then subtract the equivalent int value from current number
      while (intVal >= it->first)
      {
         romanResult = romanResult + it->second;
         intVal = intVal - it->first;
      }
   }

   return romanResult;
}

http://blog.csdn.net/havenoidea/article/details/11848921
Read full article from Integer and Roman Numeral | N00tc0d3r

Integer and Roman Numeral | N00tc0d3r

Labels

Popular Posts