Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Recommended reading

  • CSDN home page
  • GitHub open source address
  • Unity3D plugin sharing
  • Jane’s address book
  • My personal blog
  • QQ group: 1040082875

Hello, everyone, I am a little Magic dragon, Unity3D software engineer, VR, AR, virtual simulation direction, update software development skills from time to time, life perception, remember to use one button three links.

A, the title

1. Algorithm topic

“Convert the entered integer to Roman numerals.”

Title link: Source: LeetCode

Link: leetcode-cn.com/problems/in…

2

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

character The numerical
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 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. Give you an integer and convert it to Roman numerals.

Example 1: Input: num = 3 Output: "III"Copy the code
Example 2: Input: num = 48 Output: "XLVIII" Resolution: XL = 40, V = 5, III = 3Copy the code
Example 3: Input: num = 4994 Output: "MIVCMXCIV" Parse: MIV = 4000, CM = 900, XC = 90, IV = 4Copy the code

Second, the problem solving

1. Analysis of ideas

Roman numerals are made up of 7 symbols, each corresponding to a specific value, and 6 additional compound symbols are given according to the subtraction rule, for a total of 13 unique symbols, as shown below:

The key to this problem is to select the largest possible sign value when converting integers into Roman numerals, such as 140. The maximum sign value can be C = 100, and the maximum sign value XL = 40.

2. Code implementation

Violent solution:

This idea is relatively simple, because integer to Roman numerals, the number of each digit can be processed separately, using modular operation and trigger operation, you can get the number of each digit, and then corresponding to the number in Roman numerals can be combined.

public class Solution 
{
    public string IntToRoman(int num) 
    {
        string[] M = { ""."M"."MM"."MMM" }; // 1000，2000，3000
        string[] C = { ""."C"."CC"."CCC"."CD"."D"."DC"."DCC"."DCCC"."CM" }; / / 100 ~ 900
        string[] X = { ""."X"."XX"."XXX"."XL"."L"."LX"."LXX"."LXXX"."XC" }; / / 10 ~ 90
        string[] I = { ""."I"."II"."III"."IV"."V"."VI"."VII"."VIII"."IX" }; / / 1 ~ 9
        return M[num / 1000] + C[(num % 1000) / 100] + X[(num % 100) / 10] + I[num % 10]; }}Copy the code

Greedy algorithm

Greedy rule: try to use the largest number to represent each time, such as 2118, try to choose the largest number to represent each time, then 2000, 100, 10, 8, will get the correct result: MMCXVIII.

public class Solution 
{
    public string IntToRoman(int num) 
    {
        int[] values = { 1000.900.500.400.100.90.50.40.10.9.5.4.1 };
        string[] rom = { "M"."CM"."D"."CD"."C"."XC"."L"."XL"."X"."IX"."V"."IV"."I" };
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < values.Length; i++)
        {
            while(num >= values[i]) { sb.Append(rom[i]); num -= values[i]; }}returnsb.ToString(); }}Copy the code

3. Time complexity

Time complexity: O(1)

The amount of computation is independent of the size of the input number.

Space complexity: O(1)

The amount of computation is independent of the size of the input number.

Third, summary

There are two ways to solve this problem, and of course there are more ways to solve this problem, so think about it more.

The greedy rule of greedy algorithms: use the largest number at a time. Similar to the principle of converting integers to Roman numerals, fewer characters are easier to communicate with, which is probably the original intention of the people who designed Roman numerals.