Tuesday, July 15, 2014

Roman to Integer & Integer to Roman

Given a roman numeral, convert it to an integer.

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

规则:
  1. 相同的数字连写,所表示的数等于这些数字相加得到的数,例如:III = 3
  2. 小的数字在大的数字右边,所表示的数等于这些数字相加得到的数,例如:VIII = 8
  3. 小的数字,限于(I、X和C)在大的数字左边,所表示的数等于大数减去小数所得的数,例如:IV = 4
  4. 正常使用时,连续的数字重复不得超过三次
public class Solution {
    public int romanToInt(String s) {
        //Time: O(n)  Space: O(n)
        if (s == null || s.length() == 0) {
            return 0;
        }
        
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        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 res = map.get(s.charAt(s.length() - 1));
        for (int i = s.length() - 2; i >= 0; i--) {
            int cur = map.get(s.charAt(i));
            int pre = map.get(s.charAt(i + 1));
            if (cur >= pre) {
                res += cur;
            } else {
                res -= cur;
            }
        }
        return res;
    }
}
Given an integer, convert it to a roman numeral.

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

No comments:

Post a Comment