LeetCode - Medium - 12. Integer to Roman

小灰灰 2023-01-01 03:41 123阅读 0赞

## Topic ##

*  Math
 *  String

## Description ##

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

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 an integer, convert it to a roman numeral.

**Example 1**:

Input: num = 3
    Output: "III"

**Example 2**:

Input: num = 4
    Output: "IV"

**Example 3**:

Input: num = 9
    Output: "IX"

**Example 4**:

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

**Example 5**:

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

**Constraints**:

*  1 <= num <= 3999

## Analysis ##

略

## Submission ##

public class IntegerToRoman { 
    
    	// 方法一：我写的
    	public String intToRoman1(int num) { 
    		if (num < 1 || num > 3999)
    			throw new IllegalArgumentException(String.valueOf(num));
    
    		StringBuilder sb = new StringBuilder();
    		int digit = 0;
    		while (num > 0) { 
    			int n1 = num % 10;
    			if (n1 != 0) { 
    				int n2 = n1 * (int) Math.pow(10, digit);
    				sb.insert(0, map(n2));
    			}
    			digit++;
    			num /= 10;
    		}
    		return sb.toString();
    	}
    
    	private String map(int num) { 
    		if (0 < num && num <= 3)
    			return repeat("I", num);
    		if (num == 4)
    			return "IV";
    		if (5 <= num && num <= 8)
    			return "V" + repeat("I", num - 5);
    		if (num == 9)
    			return "IX";
    		if (10 <= num && num <= 30)
    			return repeat("X", num / 10);
    		if (num == 40)
    			return "XL";
    		if (50 <= num && num <= 80)
    			return "L" + repeat("X", num / 10 - 5);
    		if (num == 90)
    			return "XC";
    		if (100 <= num && num <= 300)
    			return repeat("C", num / 100);
    		if (num == 400)
    			return "CD";
    		if (500 <= num && num <= 800)
    			return "D" + repeat("C", num / 100 - 5);
    		if (num == 900)
    			return "CM";
    		if (1000 <= num && num <= 3000)
    			return repeat("M", num / 1000);
    
    		return "";
    	}
    
    	private String repeat(String str, int num) { 
    		if (num < 1)
    			return "";
    		StringBuilder sb = new StringBuilder();
    		for (int i = 0; i < num; i++) { 
    			sb.append(str);
    		}
    		return sb.toString();
    	}
    
    	// 方法二：挺巧妙的
    	public String intToRoman2(int num) { 
    		int[] values = {  1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 };
    		String[] strs = {  "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" };
    
    		StringBuilder sb = new StringBuilder();
    
    		for (int i = 0; i < values.length; i++) { 
    			while (num >= values[i]) { 
    				num -= values[i];
    				sb.append(strs[i]);
    			}
    		}
    		return sb.toString();
    	}
    
    	// 方法三：
    	public String intToRoman3(int num) { 
    		String M[] = {  "", "M", "MM", "MMM" };
    		String C[] = {  "", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM" };
    		String X[] = {  "", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC" };
    		String I[] = {  "", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX" };
    		return M[num / 1000] + C[(num % 1000) / 100] + X[(num % 100) / 10] + I[num % 10];
    	}
    
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    public class IntegerToRomanTest { 
    
    	@Test
    	public void test() { 
    		IntegerToRoman obj = new IntegerToRoman();
    
    		assertEquals("III", obj.intToRoman1(3));
    		assertEquals("IV", obj.intToRoman1(4));
    		assertEquals("IX", obj.intToRoman1(9));
    		assertEquals("LVIII", obj.intToRoman1(58));
    		assertEquals("MCMXCIV", obj.intToRoman1(1994));
    
    		assertEquals("III", obj.intToRoman2(3));
    		assertEquals("IV", obj.intToRoman2(4));
    		assertEquals("IX", obj.intToRoman2(9));
    		assertEquals("LVIII", obj.intToRoman2(58));
    		assertEquals("MCMXCIV", obj.intToRoman2(1994));
    
    		assertEquals("III", obj.intToRoman3(3));
    		assertEquals("IV", obj.intToRoman3(4));
    		assertEquals("IX", obj.intToRoman3(9));
    		assertEquals("LVIII", obj.intToRoman3(58));
    		assertEquals("MCMXCIV", obj.intToRoman3(1994));
    		
    	}
    }

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