Question

Formatted question description: https://leetcode.ca/all/13.html

 13	Roman to Integer

 Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

 Symbol       Value
 I             1
 V             5
 X             10
 L             50
 C             100
 D             500
 M             1000
 For example, two is written as II in Roman numeral, just two one's added together.
 Twelve is written as, XII, which is simply X + II.
 The number twenty seven is written as XXVII, which is XX + V + II.

 Roman numerals are usually written largest to smallest from left to right.
 However, the numeral for four is not IIII. Instead, the number four is written as IV.
 Because the one is before the five we subtract it making four.
 The same principle applies to the number nine, which is written as IX.
 There are six instances where subtraction is used:

 I can be placed before V (5) and X (10) to make 4 and 9.
 X can be placed before L (50) and C (100) to make 40 and 90.
 C can be placed before D (500) and M (1000) to make 400 and 900.
 Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.

 Example 1:

 Input: "III"
 Output: 3

 Example 2:

 Input: "IV"
 Output: 4

 Example 3:

 Input: "IX"
 Output: 9

 Example 4:

 Input: "LVIII"
 Output: 58
 Explanation: L = 50, V= 5, III = 3.

 Example 5:

 Input: "MCMXCIV"
 Output: 1994
 Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

 @tag-string

Algorithm

I-1

V-5

X-10

L-50

C-100

D-500

M-1000

  1. The same number is written consecutively, the number represented is equal to the number obtained by adding these numbers, such as: Ⅲ = 3;
  2. The small number is on the right side of the big number, and the number represented is equal to the number obtained by adding these numbers, such as: Ⅷ = 8; Ⅻ = 12;
  3. Small numbers (limited to Ⅰ, X and C) are on the left side of large numbers, and the number represented is equal to the number obtained by reducing the large number, such as: Ⅳ = 4; Ⅸ = 9;
  4. In normal use, the consecutive number shall not be repeated more than three times. (The four o’clock “IIII” on the dial is an exception)
  5. Draw a horizontal line on top of a number, which means that the number is expanded 1000 times.

There are a few things to be aware of:

  1. Any one of the basic numbers I, X, and C can not exceed three if it is used to form a number by itself or is placed on the right side of a large number; only one can be used on the left side of a large number.
  2. You can’t put any of the basic numbers V, L, D as a decimal number on the left side of the large number and use subtraction to form the number; put it on the right side of the large number and use the addition method to form the number, only one can be used.
  3. The small numbers to the left of V and X can only use Ⅰ.
  4. The small numbers to the left of L and C can only be X.
  5. Only C can be used for the small numbers on the left of D and M.

The good thing about this question is that it didn’t let us verify whether the input string is a Roman numeral, which saves a lot of effort. You need to use the HashMap data structure to convert the letters of the Roman numerals into the corresponding integer values, because the input must be a Roman numeral, so just consider two cases:

  1. if the current number is the last number, or the following number is smaller than it, the current number is added.
  2. in other cases, this number is subtracted.

Code

Java

public class Roman_to_Integer {
    class Solution {
        public int romanToInt(String s) {


            // pre-process array
            int nums[] = new int[s.length()];
            for (int i = 0; i < s.length(); i++) {
                switch (s.charAt(i)) {
                    case 'M':
                        nums[i] = 1000;
                        break;
                    case 'D':
                        nums[i] = 500;
                        break;
                    case 'C':
                        nums[i] = 100;
                        break;
                    case 'L':
                        nums[i] = 50;
                        break;
                    case 'X':
                        nums[i] = 10;
                        break;
                    case 'V':
                        nums[i] = 5;
                        break;
                    case 'I':
                        nums[i] = 1;
                        break;
                }
            }

            // sum up
            int sum = 0;
            for (int i = 0; i < nums.length - 1; i++) {
                if (nums[i] < nums[i + 1]) {
                    sum -= nums[i];
                } else {
                    sum += nums[i];
                }
            }
            return sum + nums[nums.length - 1];
        }
    }
}

All Problems

All Solutions