Leetcode-12- integer to Roman numeral (medium)

12. Integer to Roman number （ secondary ）

Roman numerals contain the following seven characters ： I, V, X, L,C,D and M.

 character            The number 
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

for example , Rome digital 2 Write to do II , Two parallel 1.12 Write to do XII , That is to say X + II . 27 Write to do XXVII, That is to say XX + V + II .

Usually , The small numbers in roman numbers are to the right of the big ones . But there are special cases , for example 4 Do not write IIII, It is IV. Numbers 1 In number 5 Left side , The number represented is equal to the large number 5 Decimal reduction 1 Value obtained 4 . similarly , Numbers 9 Expressed as IX. This special rule only applies to the following six cases ：

• I Can be placed in V (5) and X (10) Left side , To express 4 and 9.
• X Can be placed in L (50) and C (100) Left side , To express 40 and 90.
• C Can be placed in D (500) and M (1000) Left side , To express 400 and 900.

Give you an integer , Turn it into Roman numerals .

Example 1:

 Input : num = 3
 Output : "III"

Example 2:

 Input : num = 4
 Output : "IV"

Ideas ：

According to the representation of Roman numerals , Until the Roman characters have ”M”, “CM”, “D”, “CD”, “C”, “XC”, “L”, “XL”, “X”,“IX”, “V”, “IV”, “I” These kinds of , They correspond to each other 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1. If between these numbers , such as 3, Then repeat 3 Write again 1： III. So we just need to follow the Roman numeral from big to small , When num Than a[i] When I was big , cnt = num / a[i], will b[i] Connected to the s character string 串 Back cnt Time . Each cycle will num Remainder a[i], until num<=0 until ～

(1)C++

class Solution {
public:
    string intToRoman(int num) {
        int a[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4,1};
        string b[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X","IX", "V", "IV", "I"};
        string s = "";
        int index = 0, cnt;
        while(num > 0) {
            cnt = num / a[index];
            while(cnt--)
                s += b[index];
            num = num % a[index];
            index++;
        }
        return s;
    }
};

(2)python

class Solution:
    def intToRoman(self, num: int) -> str:
        a = [(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")]
        s = ''
        while num:
            for each, value  in a:
                cnt = num//each
                while(cnt):
                    s+=value
                    cnt-=1
                num = num%each
        return s