LeetCode - Easy - 13. Roman to Integer

秒速五厘米 2023-01-02 01:22 80阅读 0赞

## Topic ##

*  Math
 *  String

## Description ##

[https://leetcode.com/problems/roman-to-integer/][https_leetcode.com_problems_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, `2` is written as `II` in Roman numeral, just two one’s added together. `12` is written as `XII`, which is simply `X + II`. The number 27 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.

**Example 1**:

Input: s = "III"
    Output: 3

**Example 2**:

Input: s = "IV"
    Output: 4

**Example 3**:

Input: s = "IX"
    Output: 9

**Example 4**:

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

**Example 5**:

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

**Constraints**:

*  `1 <= s.length <= 15`
 *  `s` contains only the characters `('I', 'V', 'X', 'L', 'C', 'D', 'M')`.
 *  It is **guaranteed** that `s` is a valid roman numeral in the range `[1, 3999]`.

## Analysis ##

略

## Submission ##

public class RomanToInteger { 
    	
    	//方法一：我写的早期版本
    	public int romanToInt1(String romanNum) { 
    		int sum = 0;
    		int[] in = new int[romanNum.length()];
    		for (int i = 0; i != in.length; i++) { 
    			in[i] = map(romanNum.charAt(i));
    			if (i != 0) { 
    				if (in[i - 1] < in[i]) { 
    					in[i - 1] = -in[i - 1];
    				}
    			}
    		}
    		for (int t : in) { 
    			sum += t;
    		}
    		return sum;
    	}
    
    	//方法二：我写的，方法一的改进版
    	public int romanToInt2(String romanNum) { 
    		int sum = 0, last = Integer.MAX_VALUE;
    
    		for (int i = 0; i < romanNum.length(); i++) { 
    			int current = map(romanNum.charAt(i));
    			sum += current;
    			if (last < current)
    				sum += -2 * last;
    			last = current;
    		}
    
    		return sum;
    	}
    
    	private int map(char c) { 
    		switch (c) { 
    			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:
    				return 0;
    		}
    	}
    
    	//方法三：别人写的
    	public int romanToInt3(String s) { 
    		int res = 0;
    		for (int i = s.length() - 1; i >= 0; i--) { 
    			char c = s.charAt(i);
    			switch (c) { 
    			case 'I':
    				res += (res >= 5 ? -1 : 1);
    				break;
    			case 'V':
    				res += 5;
    				break;
    			case 'X':
    				res += 10 * (res >= 50 ? -1 : 1);
    				break;
    			case 'L':
    				res += 50;
    				break;
    			case 'C':
    				res += 100 * (res >= 500 ? -1 : 1);
    				break;
    			case 'D':
    				res += 500;
    				break;
    			case 'M':
    				res += 1000;
    				break;
    			}
    		}
    		return res;
    	}
    
    }

## Test ##

import static org.junit.Assert.*;
    
    import org.junit.Test;
    
    public class RomanToIntegerTest { 
    
    	@Test
    	public void test1() { 
    		RomanToInteger ri = new RomanToInteger();
    		assertEquals(1, ri.romanToInt1("I"));
    		assertEquals(5, ri.romanToInt1("V"));
    		assertEquals(10, ri.romanToInt1("X"));
    		assertEquals(50, ri.romanToInt1("L"));
    		assertEquals(100, ri.romanToInt1("C"));
    		assertEquals(500, ri.romanToInt1("D"));
    		assertEquals(1000, ri.romanToInt1("M"));
    		assertEquals(81, ri.romanToInt1("LXXXI"));
    		assertEquals(183, ri.romanToInt1("CLXXXIII"));
    		assertEquals(810, ri.romanToInt1("DCCCX"));
    		assertEquals(811, ri.romanToInt1("DCCCXI"));
    		assertEquals(1544, ri.romanToInt1("MDXLIV"));
    
    		assertEquals(4, ri.romanToInt1("IV"));
    		assertEquals(9, ri.romanToInt1("IX"));
    		assertEquals(3, ri.romanToInt1("III"));
    		assertEquals(58, ri.romanToInt1("LVIII"));
    		assertEquals(1994, ri.romanToInt1("MCMXCIV"));
    	}
    	
    	@Test
    	public void test2() { 
    		RomanToInteger ri = new RomanToInteger();
    		assertEquals(1, ri.romanToInt2("I"));
    		assertEquals(5, ri.romanToInt2("V"));
    		assertEquals(10, ri.romanToInt2("X"));
    		assertEquals(50, ri.romanToInt2("L"));
    		assertEquals(100, ri.romanToInt2("C"));
    		assertEquals(500, ri.romanToInt2("D"));
    		assertEquals(1000, ri.romanToInt2("M"));
    		assertEquals(81, ri.romanToInt2("LXXXI"));
    		assertEquals(183, ri.romanToInt2("CLXXXIII"));
    		assertEquals(810, ri.romanToInt2("DCCCX"));
    		assertEquals(811, ri.romanToInt2("DCCCXI"));
    		assertEquals(1544, ri.romanToInt2("MDXLIV"));
    		
    		assertEquals(4, ri.romanToInt2("IV"));
    		assertEquals(9, ri.romanToInt2("IX"));
    		assertEquals(3, ri.romanToInt2("III"));
    		assertEquals(58, ri.romanToInt2("LVIII"));
    		assertEquals(1994, ri.romanToInt2("MCMXCIV"));
    	}
    	
    	@Test
    	public void test3() { 
    		RomanToInteger ri = new RomanToInteger();
    		assertEquals(1, ri.romanToInt3("I"));
    		assertEquals(5, ri.romanToInt3("V"));
    		assertEquals(10, ri.romanToInt3("X"));
    		assertEquals(50, ri.romanToInt3("L"));
    		assertEquals(100, ri.romanToInt3("C"));
    		assertEquals(500, ri.romanToInt3("D"));
    		assertEquals(1000, ri.romanToInt3("M"));
    		assertEquals(81, ri.romanToInt3("LXXXI"));
    		assertEquals(183, ri.romanToInt3("CLXXXIII"));
    		assertEquals(810, ri.romanToInt3("DCCCX"));
    		assertEquals(811, ri.romanToInt3("DCCCXI"));
    		assertEquals(1544, ri.romanToInt3("MDXLIV"));
    		
    		assertEquals(4, ri.romanToInt3("IV"));
    		assertEquals(9, ri.romanToInt3("IX"));
    		assertEquals(3, ri.romanToInt3("III"));
    		assertEquals(58, ri.romanToInt3("LVIII"));
    		assertEquals(1994, ri.romanToInt3("MCMXCIV"));
    	}
    }

[https_leetcode.com_problems_roman-to-integer]: https://leetcode.com/problems/roman-to-integer/