Leetcode/src/com/cier/solution/array/RomanToInteger.java at master · liuenci/Leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
package com.cier.solution.array;

/**
 * I             1
 * V             5
 * X             10
 * L             50
 * C             100
 * D             500
 * M             1000
 */
// https://leetcode-cn.com/problems/roman-to-integer/description/
public class RomanToInteger {

    public static int romanToInt(String s) {
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            switch (c) {
                case 'I':
                    if (i != s.length() - 1 && s.charAt(i + 1) == 'V') {
                        count += 4;
                        i++;
                    } else if (i != s.length() - 1 && s.charAt(i + 1) == 'X') {
                        count += 9;
                        i++;
                    } else {
                        count += 1;
                    }
                    break;
                case 'V':
                    count += 5;
                    break;
                case 'X':
                    if (i != s.length() - 1 && s.charAt(i + 1) == 'L') {
                        count += 40;
                        i++;
                    } else if (i != s.length() - 1 && s.charAt(i + 1) == 'C') {
                        count += 90;
                        i++;
                    } else {
                        count += 10;
                    }
                    break;
                case 'L':
                    count += 50;
                    break;
                case 'C':
                    if (i != s.length() - 1 && s.charAt(i + 1) == 'D') {
                        count += 400;
                        i++;
                    } else if (i != s.length() - 1 && s.charAt(i + 1) == 'M') {
                        count += 900;
                        i++;
                    } else {
                        count += 100;
                    }
                    break;
                case 'D':
                    count += 500;
                    break;
                case 'M':
                    count += 1000;
                    break;
                default:
                    break;
            }
        }
        return count;
    }

    /**
     * Runtime: 4 ms, faster than 81.66% of Java online submissions for Roman to Integer.
     * Memory Usage: 36 MB, less than 99.95% of Java online submissions for Roman to Integer.
     * @param s
     * @return
     */
    public int romanToInt2(String s) {
        String[][] lookup = {
                {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"},
                {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"},
                {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"},
                {"", "M", "MM", "MMM"}
        };
        int ret = 0;
        int base = 1000;
        int x = 3;
        int y = 3;
        int pos = 0;
        while (pos < s.length()){
            if (pos + lookup[x][y].length() <= s.length()) {
                boolean wrong = false;
                for (int i = 0; i < lookup[x][y].length(); i++) {
                    if (lookup[x][y].charAt(i) != s.charAt(pos + i)){
                        wrong = true;
                        break;
                    }
                }
                if (!wrong) {
                    pos += lookup[x][y].length();
                    ret += base * y;
                }
            }
            y--;
            if (y == 0) {
                base /= 10;
                x--;
                y = 9;
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        System.out.println(romanToInt("MCMXCIV"));
    }
}