接外包,有相关需求的可以联系我:Telegram | Email

LeetCode:12. Integer to Roman

该文章创建(更新)于09/12/2020,请注意文章的时效性!

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

SymbolValue
I1
V5
X10
L50
C100
D500
M1000

For example, two is written as II in Roman numeral, just two one's added together. Twelve is written as, XII, which is simply X + II. The number twenty seven 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. Input is guaranteed to be within the range from 1 to 3999.

Example

  • Example 1:

    Input: 3
    Output: "III"

  • Example 2:

    Input: 4
    Output: "IV"

  • Example 3:

    Input: 9
    Output: "IX"

  • Example 4:

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

  • Example 5:

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

思路

  • step1:先明确罗马数字是如何生成的;
  • step2:获取每一位的数字(除留余数法???),并按照:

num = X(n)10^n + X(n-1)10^(n-1) + ........+ x(0)*10^0

得到每一位的值,例如:3965 = 3000+900+60+5;并把3000,900,60,5依倒序放到一个数组中;

  • step3:从个位数到千位数依次判断怎样来获取其罗马表达式:
数字范围用到的罗马字符
1-9I,V,X
10-99X,L,C
100-999C,D,M
1000-3000M

代码

Python

My Way

提交代码

class Solution:
    def intToRoman(self, num: int) -> str:
        # 除留余数法获取每个位的数字
        # 这里只需一个add也行
        add = []
        n = 0
        while(num):
            i = num % 10 # 用于获取余数
            num = (num - i)/10 # 去掉最后一位:去掉该原位及其获取余数后获取到的0
            # 这里只需一个add也行
            add.append(i * math.pow(10,n))
            n += 1

        #按特定逻辑顺序形成罗马字符            
        str = ''
        for x in add:
            print(x)
            if x < 10:
                if x < 4:
                    str = str + int(x) * 'I'
                elif x == 4:
                    str = 'IV'
                elif x == 5:
                    str = 'V'
                elif x > 5 and x < 9:
                    str = 'V' + int(x - 5) * 'I'
                else:
                    str = 'IX'
            elif x >= 10 and x < 99:
                if x < 40:
                    str = int(x/10) * 'X' + str
                elif x == 40:
                    str = 'XL' + str
                elif x == 50:
                    str = 'L' + str
                elif x > 50 and x < 90:
                    str = 'L' + int((x - 50)/10) * 'X' + str
                else:
                    str = 'XC' + str
            elif x >=100 and x < 999:
                if x < 400:
                    str = int(x/100) * 'C' + str
                elif x == 400:
                    str = 'CD' + str
                elif x == 500:
                    str = 'D' + str
                elif x > 500 and x < 900:
                    str = 'D' + int((x - 500)/100) * 'C' + str
                else:
                    str = 'CM' + str
            elif x >= 1000:
                str = int(x / 1000) * 'M' + str  #已知最大的千位数为3

        return str                

测试代码

import math
m = 101 # 要转换的数字
n = 0 #数字对应的位

# number_dict = {} 不能使用字典,若有两位数字相同则会发生覆盖的情况

key = []
number = []

# 这里只需一个add也行
add = []
n = 0
while(m):
    i = m % 10 # 用于获取余数
    m = (m - i)/10 # 去掉最后一位:去掉该原位及其获取余数后获取到的0
    print(str(i) + " : " + str(n))
    key.append(i)
    number.append(n)
    # 这里只需一个add也行
    add.append(i * math.pow(10,n))
    n += 1

dict = [key,number]

# print(number_dict)    

print('*********get**********')
print(dict)

# print(add)

Roman_dict =[['I','V','X'],
             ['X','L','C'],
             ['C','D','M']]

str = ''


print('***add****')
for x in add:
    print(x)

print('str')
print(int(1.0))

print("strating")

for x in add:
    print(int(x))
    if x >= 0 and x < 10:
        if x < 4:
            str = str + int(x) * 'I'
        elif x == 4:
            str = 'IV'
        elif x == 5:
            str = 'V'
        elif x > 5 and x < 9:
            str = 'V' + int(x - 5) * 'I'
        else:
            str = 'IX'
    elif x >= 10 and x < 99:
        if x < 40:
            str = int(x/10) * 'X' + str
        elif x == 40:
            str = 'XL' + str
        elif x == 50:
            str = 'L' + str
        elif x > 50 and x < 90:
            str = 'L' + int((x - 50)/10) * 'X' + str
        else:
            str = 'XC' + str
    elif x >=100 and x < 999:
        if x < 400:
            str = int(x/100) * 'C' + str
        elif x == 400:
            str = 'CD' + str
        elif x == 500:
            str = 'D' + str
        elif x > 500 and x < 900:
            str = 'D' + int((x - 500)/100) * 'C' + str
        else:
            str = 'CM' + str
    elif x >= 1000:
        str = int(x / 1000) * 'M' + str  #已知最大的千位数为3

print(str)

The best Way in Leetcode

1.多了解了一个所谓的 // 运算(取整除)方式;
2.感觉这个就是按照“阶梯”(在获取每一阶的同时进行转换)方式来获取到最终的数据,而非我那种“离散”(先获取每一阶对应的数,再绕回去进行罗马数字的转换)!哈哈!感觉自己对罗马数字的理解不太透彻!

上传代码

class Solution:
    def intToRoman(self, num: int) -> str:
        answer = ''

        ms = num // 1000
        num -= ms * 1000
        answer += ms * 'M'
        if num >= 900:
            answer += 'CM'
            num -= 900

        #print(num)
        ds = num // 500
        num -= ds * 500
        answer += ds * 'D'
        if num >= 400:
            answer += 'CD'
            num -= 400

        cs = num // 100
        num -= cs * 100
        answer += cs * 'C'
        if num >= 90:
            answer += 'XC'
            num -= 90

        ls = num // 50
        num -= ls * 50
        answer += ls * 'L'
        if num >= 40:
            answer += 'XL'
            num -= 40

        xs = num // 10
        num -= xs * 10
        answer += xs * 'X'
        if num >= 9:
            answer += 'IX'
            num -= 9

        vs = num // 5
        num -= vs * 5
        answer += vs * 'V'
        if num >= 4:
            answer += 'IV'
            num -= 4

        return answer + num * 'I'

完整测试代码

class Solution:
    def intToRoman(self, num: int) -> str:
        answer = ''

        ms = num // 1000
        num -= ms * 1000
        print(num)
        answer += ms * 'M'
        if num >= 900:
            answer += 'CM'
            num -= 900

        print(num)
        ds = num // 500
        num -= ds * 500
        print(num)

        answer += ds * 'D'
        if num >= 400:
            answer += 'CD'
            num -= 400

        print(num)
        cs = num // 100
        num -= cs * 100
        print(num)
        answer += cs * 'C'
        if num >= 90:
            answer += 'XC'
            num -= 90

        print(num)

        ls = num // 50
        num -= ls * 50
        print(num)
        answer += ls * 'L'
        if num >= 40:
            answer += 'XL'
            num -= 40

        print(num)

        xs = num // 10
        num -= xs * 10
        print(num)

        answer += xs * 'X'
        if num >= 9:
            answer += 'IX'
            num -= 9
        print(num)

        vs = num // 5
        num -= vs * 5
        print(num)

        answer += vs * 'V'
        if num >= 4:
            answer += 'IV'
            num -= 4
        print(num)

        return answer + num * 'I'

S = Solution()
print(S.intToRoman(1998))

JAVA

原理同上

提交代码

class Solution {
    public String intToRoman(int num) {
            String answer = "";

            int ms = num / 1000;
            num -= ms * 1000;
            answer += n_array(ms,"M");
            if (num >= 900){
                answer += "CM";
                num -= 900;
            }


            int ds = num / 500; // 500
            num -= ds * 500;
            answer += n_array(ds,"D");
            if (num >= 400){
                answer += "CD";
                num -= 400;
            }


            int cs = num / 100 ;// 100
            num -= cs * 100;
            answer += n_array(cs,"C");
            if(num >= 90){
                answer += "XC";
                num -= 90;
            }

            int ls = num / 50 ;
            num -= ls * 50;
            answer += n_array(ls,"L");
            if (num >= 40){
                answer += "XL";
                num -= 40;
            }

            int xs = num / 10 ;
            num -= xs * 10;
            answer += n_array(xs,"X");
            if (num >= 9){
                answer += "IX";
                num -= 9;
            }

            int vs = num / 5; // 5
            num -= vs * 5;
            answer += n_array(vs,"V");
            if (num >= 4){
                answer += "IV";
                num -= 4;
            }

            return answer + n_array(num,"I");

        }

    public static String n_array(int n, String s){
        String M = "";

        while(n > 0){
            M = M + s;
            n--;
        }

        return M;
    }
}

测试代码

public class roman {
    static class Solution {
        public String intToRoman(int num) {
            String answer = "";

            int ms = num / 1000;
            num -= ms * 1000;
            answer += n_array(ms, "M");
            if (num >= 900) {
                answer += "CM";
                num -= 900;
            }


            int ds = num / 500; // 500
            num -= ds * 500;
            answer += n_array(ds, "D");
            if (num >= 400) {
                answer += "CD";
                num -= 400;
            }


            int cs = num / 100;// 100
            num -= cs * 100;
            answer += n_array(cs, "C");
            if (num >= 90) {
                answer += "XC";
                num -= 90;
            }

            int ls = num / 50;
            num -= ls * 50;
            answer += n_array(ls, "L");
            if (num >= 40) {
                answer += "XL";
                num -= 40;
            }

            int xs = num / 10;
            num -= xs * 10;
            answer += n_array(xs, "X");
            if (num >= 9) {
                answer += "IX";
                num -= 9;
            }

            int vs = num / 5; // 5
            num -= vs * 5;
            answer += n_array(vs, "V");
            if (num >= 4) {
                answer += "IV";
                num -= 4;
            }

            return answer + n_array(num, "I");

        }
    }

    public static void main(String [] args){
        Solution S = new Solution();
        System.out.println(S.intToRoman(100));
    }

    public static String n_array(int n, String s){
        String M = "";

        while(n > 0){
            M = M + s;
            n--;
        }

        return M;
    }

}

The Way in LeetCode

这里把我们上面的循环选择判断给简化到最低了!

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

要不赞赏一下?

微信
支付宝
PayPal
Bitcoin

版权声明 | Copyright

除非特别说明,本博客所有作品均采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可。转载请注明转自-
https://www.emperinter.info/2020/09/12/integer-to-roman/


要不聊聊?

我相信你准备留下的内容是经过思考的!【勾选防爬虫,未勾选无法留言】

*

*



微信公众号

优惠码

阿里云国际版20美元
Vultr10美元
搬瓦工 | Bandwagon应该有折扣吧?
域名 | namesiloemperinter(1美元)