[LintCode] Integer to Roman & Roman to Integer

pkwenda 發(fā)布于2019-08-14 15:15 / 789人閱讀

摘要：建立映射整數(shù)數(shù)組字符串?dāng)?shù)組，這兩個(gè)數(shù)組都要從大到小，為了方便之后對(duì)整數(shù)進(jìn)行從大到小的分解，以便用從前向后建立數(shù)字。建立，存入的數(shù)值對(duì)應(yīng)關(guān)系。

Problem

Integer to Roman
Given an integer, convert it to a roman numeral.
The number is guaranteed to be within the range from 1 to 3999.

Roman to Integer
Given a roman numeral, convert it to an integer.
The answer is guaranteed to be within the range from 1 to 3999.

Symbol   Value
I        1
V        5
X        10
L        50
C        100
D        500
M        1,000

Note

Integer to Roman:

建立映射：整數(shù)數(shù)組num -- 字符串?dāng)?shù)組roman，這兩個(gè)數(shù)組都要從大到小，為了方便之后對(duì)整數(shù)n進(jìn)行從大到小的分解，以便用StringBuilder()從前向后建立Roman數(shù)字。

Roman to Integer:

建立HashMap，存入Roman的數(shù)值對(duì)應(yīng)關(guān)系。然后從String s從前向后遍歷每個(gè)字符，找到map對(duì)應(yīng)的值累加，if遇到前一位值小于后一位值的情況，減去前一位值的2倍（if外面多加了一次，減2倍減回來）。

Solution

Integer to Roman

public class Solution {
    public String intToRoman(int n) {
        // Write your code here
        String[] roman = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        int[] num = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        StringBuilder sb = new StringBuilder();
        int i = 0;
        while (n != 0) {
            if (n >= num[i]) {
                sb.append(roman[i]);
                n -= num[i];
            }
            else i++;
        }
        return sb.toString();
    }
}

Roman to Integer

public class Solution {
    public int romanToInt(String s) {
        HashMap map = new HashMap();
        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++) {
            res += map.get(s.charAt(i));
            if (i > 0 && map.get(s.charAt(i-1)) < map.get(s.charAt(i))) 
                res -= 2 * map.get(s.charAt(i-1));
        }
        return res;
    }
}