Original address: http://blog.leanote.com/post/dawnmagnet/d23f1485c8a4

subject

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

character          numerical value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, the Roman numeral 2 is written as II, which means two parallel ones. 12 write XII, that is X + II. 27 write XXVII, that is XX + V + II.

Usually, the small numbers in Roman numerals are to the right of the large numbers. But there are some special cases. For example, 4 is not written as IIII, but IV. The number 1 is on the left side of the number 5, which is equal to the number 4 obtained by subtracting the decimal 1 from the large number 5. Similarly, the number 9 is denoted by IX. This special rule only applies to the following six cases:

I can be placed to the left of V (5) and X (10) to represent 4 and 9.
X can be placed to the left of L (50) and C (100) to represent 40 and 90.
C can be placed to the left of D (500) and M (1000) to represent 400 and 900.
I'll give you an integer and turn it into Roman numerals.

Example 1:

input: num = 3
 output: "III"
Example 2:

input: num = 4
 output: "IV"
Example 3:

input: num = 9
 output: "IX"
Example 4:

input: num = 58
 output: "LVIII"
explain: L = 50, V = 5, III = 3.
Example 5:

input: num = 1994
 output: "MCMXCIV"
explain: M = 1000, CM = 900, XC = 90, IV = 4.
 

Tips:

1 <= num <= 3999

Source: LeetCode
Link: https://leetcode-cn.com/problems/integer-to-roman
The copyright belongs to Lingkou network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

Thinking analysis

For this problem, through observation, we can conclude that roman numbers and each digit are one-to-one correspondence. It can be seen from the explanation in the title that it is divided according to the digit. For example, in example 5, the numbers of the thousandth, the hundredth, the tenth and the individual are respectively corresponding to some letter combinations.
We can also use this method.
Let's analyze the single digits first. There are only ten in all. I suggest that students who won't do it should list them
0|1|2|3|4|5|6|7|8|9
–|
No I|II|III|IV|V|VI|VII|VIII|IX

It's not hard to see that it's regular. We divided them into five groups, 1-3,4,5,6-8,9
Let's make a list of the tenth
0|1|2|3|4|5|6|7|8|9
–|
No | x | XX | XXX | XL | L | LX | LXX | L | XC
It's not hard to see that it's a replacement of soup without dressing
The IVX is replaced by XLC, without any technical content
So we can deal with each digit separately, and finally put them together.

C + + code

class Solution {
public:
    string intToRoman(int num) {
        const string cdr = "IVXLCDM--";
        string res;
        for (int i = 0; i < 4 && num > 0; ++i) {
            int left = num % 10;
            num /= 10;
            if (left <= 3) 
                res += string(left, cdr[i * 2]);
            else if (left <= 4) {
                res += cdr[i * 2 + 1];
                res += cdr[i * 2];
            } else if (left <= 8)
                res += string(left - 5, cdr[i * 2]) + cdr[i * 2 + 1];
            else {
                res += cdr[i * 2 + 2];
                res += cdr[i * 2];
            }
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

Rust code

impl Solution {
    pub fn int_to_roman(mut num: i32) -> String {
        let cdr = ['I', 'V', 'X', 'L', 'C', 'D', 'M', '-', '-'];
        let mut res = String::new();
        for i in 0..4 {
            let left = num as usize % 10;
            num /= 10;
            if left <= 3 {
                for j in 0..left {
                    res.push(cdr[i * 2]);
                }
            } else if left <= 4 {
                res.push(cdr[i * 2 + 1]);
                res.push(cdr[i * 2]);
            } else if left <= 8 {
                for j in 5..left {
                    res.push(cdr[i * 2]);
                }
                res.push(cdr[i * 2 + 1]);
            } else {
                res.push(cdr[i * 2 + 2]);
                res.push(cdr[i * 2]);
            }
            if num == 0 {
                break;
            }
        }
        res.chars().rev().collect()
    }
}