leetcode: Integer to Roman

问题描述：

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

原问题链接：https://leetcode.com/problems/integer-to-roman/

 

问题分析

     在分析问题前，我们先看一下罗马数字的定义和规则，可以参照如下的链接：https://en.wikipedia.org/wiki/Roman_numerals

罗马数字里基本的数制如下：

I: 1
V: 5
X: 10
L: 50
C: 100
D: 500
M: 1000

字母可以重复，但不超过三次，当需要超过三次时，用与下一位的组合表示：
I: 1, II: 2, III: 3, IV: 4 V: 5 VI:6 VII: 7 VIII: 8 IX: 9 X:10
C: 100, CC: 200, CCC: 300, CD: 400

    按照这些定义的规则我们会发现,用罗马数字所能表示的数字范围是1 - 3999。假设在正常的值范围内，我们要将一个整数转换成罗马数字，该采用什么样的方法呢？一个比较直观的办法就是从最高可以表示的数字的基数开始，比如1000， 也就是M。用这个数去除以M，如果得到的结果不为0，则用若干个M表示这个值。当然不过3。比如结果是1，则用M表示，2则用MM表示，3就用MMM。对于百位的数字也类似，剩下的值无非就是0到9，对于0来说，就是返回一个空字符串，而对于其他的数字可以用一个数组来表示。每个数组的索引对应除得的值，而对应的值则是该除得值的字符串表示形式。

    所以按照这个思路可以得到一种如下的方法：

 

public class Solution {
    public String intToRoman(int num) {
        String[] t = {"", "M", "MM", "MMM"};
        String[] h = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
        String[] d = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
        String[] u = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
        StringBuilder result = new StringBuilder();
        result.append(t[num / 1000]).append(h[(num % 1000) / 100]).append(d[(num % 100) / 10]).append(u[num % 10]);
        return result.toString();
    }
}

     这种方式保存了千位，百位，十位和个位的每个位置的映射字符。每当当前值除以对应的位基数则将得到的值取出来，然后将值拼成一个串。

    除了上述的这种思路，还有一种办法，就是对不同基数的值进行循环相减的方法。比如对一个数字2394来说，它先对最高位的基数1000来相减，首先减去1000，得到1394，这样就在结果里放一个M，然后再减去1000，这样结果是394,表示的结果是MM。到百位的时候我们得到MMCC。可是这个时候到10位的时候，因为是数字9，我们不能连续放9个X而应该放一个XC。所以这说明我们不能用单纯的1000,100,10等这几个基数。否则会有一些遗漏。像后面的数字4也是，我们需要找到对应的数字来匹配。而对于其他的数字呢？我们可以用相应数字重复几次来表示。所以对于个位数的数字来说，我们应该依次考察的数字是9, 5, 4, 1。10位和100位的也类似。

    这样我们就建立了一个基数列表 int[] value = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1} 每次用输入值减去当前位置的值，如果不为0则在添加一个该数字对应的字符串。这样我们也应该同时定义一个对应的字符串数组 String[] symbol = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"}; 我们首先从最高位的基数1000开始，用输入值和它比较，如果输入值大于它，则减去这个基数值并添加对应的字符串。这样我们利用了两个循环来逐步从高位向低位遍历相减。最终的代码实现如下：

 

public class Solution {
    public String intToRoman(int num) {
        StringBuilder builder = new StringBuilder();
        String[] symbol = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        int[] value = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        for(int i = 0; num != 0; i++) {
            while(num >= value[i]) {
                num -= value[i];
                builder.append(symbol[i]);
            }
        }
        
        return builder.toString();
    }
} 

 

总结

    个人觉得建立一个针对各位的映射表并根据各位的值取最终结果的方式最直观。从理论上来说它的时间复杂度为常量。建立数值映射表的方式虽然空间花费更大一点，但是时间效率更高。