Roman to Integer/Integer to Roman

Leave a comment

February 13, 2017 by oneOokay

roman numerals chart

http://literacy.kent.edu/Minigrants/Cinci/romanchart.htm

罗马字表:

I = 1; V = 5; X = 10; L = 50; C = 100; D = 500; M = 1000

IV = 4; IV = 9; XL = 40; XC = 90; CD = 400; CM = 900

e.g.: 1954 as MCMLIV; 1990 as MCMXC


Integer to Roman:

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.


两种方法:

  1. 把1000-4000, 100-900,10-90,1-9都用罗马数字表示出来,存到array里面,然后直接转换.
  2. 把”特殊”的罗马数字存一个array,把其相对应的数字存一个array,慢慢减(相当于正常里面的%)
public String intToRoman(int num) {
    String M[] = {"", "M", "MM", "MMM"};
    String C[] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
    String X[] = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
    String I[] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
    return M[num / 1000] + C[(num % 1000) / 100] + X[(num % 100) / 10] + I[(num % 10)];
}
public String intToRoman(int num) {
//把每个都看成一个个体,他们互相之间是不能够append的.
    String[] roman = {"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 };
    int i = 0;
    StringBuilder sb = new StringBuilder();
    while (num > 0){
	while (num >= values[i]){
	   sb.append(roman[i]);
	   num -= values[i];
	}
	i ++;
    }  
   return sb.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.


从string的最右开始遍历:

  • 用pre存前一个数
  • 如果pre>cur:说明当前的cur是要被减掉的
  • 如果pre<cur:说明当前的cur是要被加上的
public int romanToInt(String s) {
        Map<Character, Integer> map = new HashMap<>();
        map.put('I', 1);
        map.put('V', 5);
        map.put('X', 10);
        map.put('L', 50);
        map.put('C', 100);
        map.put('D', 500);
        map.put('M', 1000);
        
        int i = s.length() - 1;
        int res = 0;
        int cur = 0;
        int pre = 0;
        while (i >= 0){
            cur = map.get(s.charAt(i));
            if (cur >= pre) res += cur;
            else res -= cur;
            pre  = cur;
            i --;
        }
        return res;
    }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: