Integer to Roman, Leetcode 解题笔记

Given an integer, convert it to a roman numeral.

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

咱中国人对罗马数字不熟悉,基本也就是10以内的水平。欲解此题,必须先科普:

罗马数字的符号一共只有7个:I(代表1)、V(代表5)、X(代表10)、L(代表50)、C代表100)、D(代表500)、M(代表1,000)。这7个符号位置上不论怎样变化,它所代表的数字都是不变的。它们按照下列规律组合起来,就能表示任何数:
1.重复次数:一个罗马数字符号重复几次,就表示这个数的几倍。如:”III”表示”3″;”XXX”表示”30″。
2.右加左减:一个代表大数字的符号右边附一个代表小数字的符号,就表示大数字加小数字,如”VI”表示”6″,”DC”表示”600″。一个代表大数字的符号左边附一个代表小数字的符号,就表示大数字减去小数字的数目,如”IV”表示”4″,”XL”表示”40″,”VD”表示”495″。

开始的想法是只列出上述7个符号,但后来写code的过程中发现处理特殊情况4,9等数字时操作比较繁琐,于是找到了下面的方法:
列出所有特殊值,然后从1000开始,比较num是否大于1000,如果大于,写个M,然后num – 1000后再比较,如果小于1000了,开始比较900,依此规律直到最后。

public class Solution {
    public String intToRoman(int num) {
        String[] dic = {"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};
        int i = 0;
        StringBuilder ret = new StringBuilder();
        while(i < value.length){
            if(num >= value[i]){
                ret.append(dic[i]);
                num -= value[i];
            }
            else{
                i++;
            }
        }
        return ret.toString();
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s