12. Integer to Roman，整数转罗马数字

Last Updated: 2023-09-30 07:42:40 Saturday

-- TOC --

题目分析
思路
Python
C++
C

将一个整数转换成罗马数字的表达形式。

仔细看看古代罗马人是如何计数的...

题目分析

罗马数字有如下这些符号：

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

转换规则：

For example, 2 is written as II in Roman numeral, just two one's added together. 12 is written as XII, which is simply X + II. The number 27 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.

例如：

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

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

Constraints: 1 <= num <= 3999

古代罗马很强大，但这个计数体系，如果要数很大的数，是非常费劲的...

思路

没啥特别的算法，查表是比较快的，预先将每位数字的每一种可能表达，都放在表中，然后将输入的每一位计算出来，查表，拼接字符串。这个表是固定的，不用动态计算。

Python

学习一下Python的divmod这个接口的用法，同时得到商和余数：

T = {0:'',
     1:'I', 2:'II', 3:'III', 4:'IV', 5:'V',
     6:'VI', 7:'VII', 8:'VIII', 9:'IX',
     10:'X', 20:'XX', 30:'XXX', 40:'XL', 50:'L',
     60:'LX', 70:'LXX', 80:'LXXX', 90:'XC',
     100:'C', 200:'CC', 300:'CCC', 400:'CD', 500:'D',
     600:'DC', 700:'DCC',800:'DCCC', 900:'CM',
     1000:'M', 2000:'MM', 3000:'MMM'}


class Solution:
    def intToRoman(self, num: int) -> str:
        roman = ''
        s = 1
        while num:
            num, r = divmod(num, 10)
            roman = T[r*s] + roman
            s *= 10
        return roman

速度居中，学习一下排名第一的写法：

RT =((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'))


class Solution:
    def intToRoman(self, num: int) -> str:
        roman = ''
        for k,s in RT:
            while num >= k:
                roman += s
                num -= k
        return roman

我更喜欢这个算法，有一种精妙的美！

C++

static vector<pair<int,string>> RT{{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"}};


class Solution {
public:
    string intToRoman(int num) noexcept{
        string roman;
        for(auto &[k,s]: RT)
            while(num >= k){
                roman += s;
                num -= k;
            }
        return roman;
    }
};

C

用了一块小小的static memory，否则malloc后怎么free！

static int knum[] = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
static char *ks[] = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
static char rtv[64];

char * intToRoman(int num){
    *rtv = 0;
    for(int i=0; i<sizeof(knum)/sizeof(int); ++i)
        while(num >= knum[i]){
            strcat(rtv, ks[i]);
            num -= knum[i];
        }
    return rtv;
}

本文链接：https://cs.pynote.net/ag/leetcode/202306181/

-- EOF --

-- MORE --