Learning algorithm is very important, and then to learn algorithm, a lot of practice is essential, LeetCode is a website I often go to brush questions, the topic is very detailed, each label has the topic, you can practice as a whole, this public account will take you to do the algorithm questions above.

Official link: leetcode-cn.com/problemset/…

A, the question

Difficulty: Medium

Leetcode-cn.com/problems/in…

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.

The sample

Input: 3 Output: "III" Input: 4 Output: "IV" Input: 9 Output: "IX" Input: 58 Output: "LVIII" Explanation: L = 50, V = 5, III = 3. Description: M = 1000, CM = 900, XC = 90, IV = 4.Copy the code

Tip:

  • 1 <= num <= 3999

Second, the problem solving

Method 1: greedy

Ideas:

The sequence required to convert a given integer into A Roman numeral is arranged in order of largest to smallest. Add up according to the sign value.

Code:

Class Solution {public String intToRoman(int num) {[] nums = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}; String[] str = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"}; StringBuilder sb = new StringBuilder(); int i = 0; While (num >= nums[I]){sb.append(STR [I]); num -= nums[i]; } // If there is no match, move backward and find the next maximum value. } return sb.tostring (); }}Copy the code

Complexity analysis:

  • Time complexity: O(1)

  • Space complexity: O(1)

Here are two learning resources I collected. If you need them, please give me a start. Thank you

Computer e-books warehouse: github.com/unidentifia…

Java learning video reference: github.com/unidentifia…