12. 整數轉羅馬數字（Integer to Roman）

• 題解
• • 貪心算法
  • • 複雜度分析
    • Python
    • Java(待完成)

題解

顯然的想法，和湊零錢的問題一樣，每次選擇最大的，可以保證用的羅馬字元最少且最終的組合唯一。

貪心算法

1. 初始化詞典 n u m t o c h a r = { 1 : " I " , ⋯   , 1000 : " M " } numtochar=\{1:"I",\cdots,1000:"M"\} numtochar={1:"I",⋯,1000:"M"}，儲存可用的字元。
2. 對于可以選擇的數值 k e y key key，我們使用貪心政策，從大到小選，即從 1000 1000 1000到 1 1 1：
   • 若 n u m = = 0 num==0 num==0：則退出
   • 定義 t m p = n u m / / k e y tmp=num//key tmp=num//key，表示使用目前數值幾次
   • 若 t m p = = 0 tmp==0 tmp==0，表示 n u m < k e y num<key num<key，是以跳過
   • 在 r e s res res中加入 t m p tmp tmp個 k e y key key對應的羅馬數字。
   • 更新 n u m = n u m − t m p ∗ k e y num=num-tmp*key num=num−tmp∗key
3. 傳回 r e s res res

複雜度分析

• 時間複雜度： O ( 1 ) O(1) O(1)
• 空間複雜度： O ( 1 ) O(1) O(1)

Python

class Solution:
    def intToRoman(self, num: int) -> str:
        num_dict={1:'I',
            4:'IV',
            5:'V',
            9:'IX',
            10:'X',
            40:'XL',
            50:'L',
            90:'XC',
            100:'C',
            400:'CD',
            500:'D',
            900:'CM',
            1000:'M' }
        res=""
        for key in sorted(num_dict.keys())[::-1]:
            if(num==0):
                break
            tmp=num//key
            if(tmp==0):
                continue
            res+=num_dict[key]*(tmp)
            num-=key*(tmp)
        return res
           

Java(待完成)