preface

Rare a “selection of problem solution”, then conveniently hair it.

The title

Roman numerals contain the following seven characters: I, V, X, L, C, D and M.

character The numerical
I 1
V 5
X 10
L 50
C 100
D 500
M 1000

For example, the Roman numeral 2 is written as II, which is two ones side by side. Write XII as X + II. Write XXVII as XX + V + II.

Usually, the smaller Roman numerals are to the right of the larger numerals. But there are exceptions, for example, 4 is not written as IIII, it’s written as IV. The number 1 is to the left of the number 5 and represents the number 4 when the larger number 5 decreases by 1. Similarly, the number 9 represents IX. This particular rule applies only to the following six situations:

  • I can be put to the left of V (5) and X (10) to represent 4 and 9.
  • X can be placed to the left of L (50) and C (100) to represent 40 and 90.
  • C can be put to the left of D (500) and M (1000) to represent 400 and 900. Given a Roman numeral, convert it to an integer. Make sure the input is in the range of 1 to 3999.

Example 1:

Input: "III" Output: 3Copy the code

Example 2:

Input: "IV" Output: 4Copy the code

The problem solving

Execution time :4 ms, beating 99.93% of users memory consumption in all Java commits :36.1 MB, beating 98.73% of users in all Java commits

According to the description of the title, the following rules can be summarized:

  1. Roman numerals are made up ofI,V,X,L,C,D,MA;
  2. When a small value is to the left of a large value, the value decreases, e.gIV=5-1=4;
  3. When the small value is to the right of the large value, the small value is added, as inVI=5+1=6;
  4. The rvalue is always positive, so the last digit must be positive.

In short, putting a small value to the left of a large value is subtraction, otherwise addition.

In code implementation, you can look back one bit and compare the size of the current bit with that of the next bit to determine whether the current bit is added or subtracted. When there is no next digit, add.

The value of the current bit can also be reserved. When traversing to the next bit, the reserved value can be determined as plus or minus by comparing the relationship between the reserved value and the traversal bit size. We can add the last digit.

import java.util.*;

class Solution {
    public int romanToInt(String s) {
        int sum = 0;
        int preNum = getValue(s.charAt(0));
        for(int i = 1; i < s.length(); i ++) {int num = getValue(s.charAt(i));
            if(preNum < num) {
                sum -= preNum;
            } else {
                sum += preNum;
            }
            preNum = num;
        }
        sum += preNum;
        return sum;
    }
    
    private int getValue(char ch) {
        switch(ch) {
            case 'I': return 1;
            case 'V': return 5;
            case 'X': return 10;
            case 'L': return 50;
            case 'C': return 100;
            case 'D': return 500;
            case 'M': return 1000;
            default: {
                // You can throw an exception here, but it won't come here anyway
                return 0}; }}}Copy the code
  • Conversion of Roman numerals to whole numbers
  • Roman numerals are converted to whole numbers