Topic describes

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

Character values I 1 V 5 X 10 L 50 C 100 D 500 M 1000Copy the code

For example, the Roman numeral 2 is written as II, which is two ones side by side. Write XII as X + II. Write XXVII as XX + V + II.

Usually, the smaller Roman numerals are to the right of the larger numerals. But there are exceptions, for example, 4 is not written as IIII, it’s written as IV. The number 1 is to the left of the number 5 and represents the number 4 when the larger number 5 decreases by 1. Similarly, the number 9 represents IX. This particular rule applies only to the following six situations:

  • I can be put 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 put to the left of D (500) and M (1000) to represent 400 and 900.

Given an integer, convert it to a Roman numeral. Make sure the input is in the range of 1 to 3999.

Example 1:

Input: 3 Output: "III"Copy the code

Example 2:

Input: 4 Output: "IV"Copy the code

Example 3:

Input: 9 Output: "IX"Copy the code

Example 4:

Input: 58 Output: "LVIII" Explanation: L = 50, V = 5, III = 3Copy the code

Example 5:

Description: M = 1000, CM = 900, XC = 90, IV = 4.Copy the code

Greedy method

We can list a finite number of Roman characters and their corresponding values.

Then build Roman numerals from left to right, building the highest Roman characters first (try to build “M” if you have enough points, try to build “CM” if you don’t have enough points…). :

class Solution {
    int[] val = new int[] {1000.900.500.400.100.90.50.40.10.9.5.4.1};
    String[] str = new String[]{"M"."CM"."D"."CD"."C"."XC"."L"."XL"."X"."IX"."V"."IV"."I"};
    public String intToRoman(int x) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < val.length && x > 0; i++) {
            int cv = val[i];
            String cs = str[i];
            while(x >= cv) { sb.append(cs); x -= cv; }}returnsb.toString(); }}Copy the code

Time complexity: The amount of computation is proportional to the length of the final Roman numeral. The Roman numeral is represented by a maximum of four letters for each Arabic numeral (e.g. VIII = 8), so the length of the Roman numeral cannot exceed four times the length of the Arabic numeral (within the same order of magnitude). Arabic numerals are about logN in length, so Roman numerals are no longer than 4 * logN. The complexity is O(logn) (remember complexity ignores constants)

Spatial complexity: Although two arrays are used to record Roman characters and values, the amount of space consumed is fixed and does not vary with sample size. The complexity is order one.

The last

This is the 12th article in our “Brush through LeetCode” series, which started on 2021/01/01. As of the start date, there are 1916 questions in LeetCode, some of which have lock questions. We will finish all the questions without lock first.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

As the number of LeetCode questions keeps increasing with weekly and biweekly competitions, in order to facilitate our progress statistics, we will calculate the progress according to the total number of questions at the beginning of the series as the denominator and the completed questions as the numerator. Current progress is 12/1916.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: Github address & Gitee address.

In the repository, you’ll see links to the series, the corresponding code for the series, the LeetCode source links, and some other preferred solutions.


# Algorithms and data structures

# LeetCode antithesis

# Algorithmic interview