LeetCode_Python(12)_整数からローマ数字へ

2670 ワード

需要
ローマ数字には、I、V、X、L、C、D、Mの7文字が含まれています.
ローマ文字
対応する数値
I
1
V
5
X
10
L
50
C
100
D
500
M
1000
例えば、ローマ数字2はIIと書かれており、2つの並列の1である.12はXIIと書きます.つまりX+IIです.27 XXVIIと書くと、XX+V+IIとなります.
通常、ローマ数字の中で小さい数字は大きな数字の右側にあります.しかし、例えば4はIIIではなくIVと書くという特例もある.数字1は数字5の左側にあり、表す数は大数5から小数1を減らした数値4に等しい.同様に、数字9はIXとして表される.この特殊な規則は以下の6つの場合にのみ適用される:IはV(5)とX(10)の左側に置いて4と9を表すことができる.XはL(50)とC(100)の左側に置いて40と90を表すことができる.CはD(500)とM(1000)の左側に置いて400と900を表すことができる.
整数を与え、ローマ数字に変換します.入力は1~3999の範囲であることを確認します.
例1入力:3出力:「III」
例2入力:4出力:「IV」
例3入力:9出力:「IX」
例4入力:58出力:「LVIII」解釈:L=50,V=5,III=3
例5入力:1994出力:「MCMXCIV」解釈:M=1000、CM=900、XC=90、IV=4
方法1:暴力法
  • は数値を文字列に変換し、反転し、最大ビット数(個百千)に対応するインデックス値の最大を実現する.
  • は文字列を逆順に遍歴し、最大ビット数からビット毎に取り出して判断することを実現し、需要に応じて千ビット数は3にしか取れず、10百ビットに4、9の特殊な状況が存在し、変換規則が一致し、ビット数の判断を通じて、[0, 4, 9]に分けて異なる値を取ることができる.
  • この方法はLeetCode上の136 msで93%のユーザーを負かし、考えやすいが、コードが簡潔ではない.
  • 参照コード
  • def into_to_roman(n):
        roman_num= ['I', 'V', 'X', 'L', 'C', 'D', 'M']
        num = str(n)[::-1]
        r = ''
        for i in range(len(num)-1, -1, -1):
            if i == 3:
                r += int(num[i]) * roman_num[i*2]
            else:
                if int(num[i]) == 0:
                    r += ''
                elif int(num[i]) < 4:
                    r += int(num[i]) * roman_num[i*2]
                elif int(num[i]) == 4:
                    r += roman_num[i*2] + roman_num[i*2 + 1]
                elif int(num[i]) < 9:
                    r += roman_num[i*2 + 1] + (int(num[i]) - 5) * roman_num[i*2]
                else:
                    r += roman_num[i*2] + roman_num[i*2 + 2]
        return r 
    
    a = 1994
    print(into_to_roman(a))
    MCMXCIV
    

    方法2:辞書の構築
  • 整数とローマ数字に対応する辞書を構築し、すべての特殊な状況を加える.
  • 辞書を遍歴し、整数を辞書のkeyで割って下に整数を取り、対応する桁数の値を得、さらにその桁数のローマ数字を得て、整数に今回の遍歴の数値を減算するように再付与し、次の遍歴を継続する.
  • 特に注意して、ビット数値が0の場合を判断する必要があり、処理をしなければならない.
  • 参照コード
  • def into_to_roman(n):
        r = ''
        ir = {'1000': 'M', '900': 'CM', '500': 'D', '400': 'CD', '100': 'C', '90': 'XC', '50': 'L',
              '40': 'XL', '10': 'X', '9': 'IX', '5': 'V', '4': 'IV', '1': 'I'}
    
        for k, v in ir.items():
            tmp = n // int(k)
            if tmp != 0:
                r += tmp * v
                n -= tmp * int(k)
        return r
    
    a = 3994
    print(into_to_roman(a))
    MMMCMXCIV