LeetCode-13. Roman numeral to integer (day3)

Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit series activities – click on the task to see the details of the activities.

I. Preface:

👨🎓 Author: Bug Bacteria

✏️ blog: CSDN, Nuggets, etc

💌 public account: Magic House of the Circle of the Apes

🚫 special statement: original is not easy, reprint please attach the original source link and this article statement, thank you for your cooperation.

🙏 Copyright notice: part of the text or pictures in the article may come from the Internet or Baidu Encyclopedia, if there is infringement, please contact bug bacteria processing.

Hello, little friends, I am bug bacteria 👀. Gold three silver four, brush the month again. So whether you’re looking for a career change or a career change, get your act together and do the right thing 👣. So, quickly follow the pace of bug bacteria roll up ⏰, strong from this moment! ➕ 🧈

In the process of reviewing articles, if you think the articles are helpful to you at all, please don’t be too mean with your likes and bravely light up the articles 👍. Your likes (collect ⭐️+ pay attention to 👨 port + message board) are the best encouragement and support for bugs on my creation path. Time does not abandon 🏃🏻♀️, nuggets stop 💕, cheer up 🏻

Ii. Title Description:

Difficulty: ⭐ ⭐

Given a Roman numeral, convert it to an integer.

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

Such as:

The Roman numeral 2 is written as II, as 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 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 put to the left of D (500) and M (1000) to represent 400 and 900.

Example 1:

Input: s = "III" Output: 3Copy the code

Example 2:

Input: s = "IV" Output: 4Copy the code

Example 3:

Input: s = "IX" Output: 9Copy the code

Title: LeetCode website

Iii. Analysis of Ideas:

Well, the best way to do this is to enumerate numbers through a map, and then iterate over Roman numerals, so the best way to do this is to add and subtract from left to right.

So the general rule is that if the smaller Roman numeral is to the right of the larger numeral, and if the string satisfies that condition, then each character can be treated as a single value, adding up the corresponding value of each character.

For example XXVI can be seen as X+X+V+I=10+10+5+1=26.

If the Roman numeral has a smaller numeral to the left of the larger numeral, the smaller numeral must be subtracted. In this case, we can also treat each character as a single value, and if the number to the right of a number is larger than itself, we can simply subtract that number.

For example, XIV can be taken as X−I+V=10−1+5=14.

Specific implementation can be as follows:

Define a map of all Roman numerals. Such as the put (‘ I ‘, 1); put(‘V’, 5);
Compare whether the next number is larger or smaller than the current number, and subtract the smaller number.

Iv. Algorithm implementation:

AC code

The specific algorithm is as follows:

<Character, Integer> lmMap = new HashMap<Character, Integer>() {{put('I', 1); put('V', 5); put('X', 10); put('L', 50); put('C', 100); put('D', 500); put('M', 1000); }}; Public int romanToInt(String s) {// int ans = 0; for (int i = 0; i < s.length(); Int value = lmmap.get (s.charat (I)); // From left to right, compare directly with the next digit; If (I < s.length() -1 && value < lmmap.get (s.charat (I + 1)))) {ans -= value; } else { ans += value; } } return ans; }}Copy the code

V. Summary:

The screenshot of leetcode submission results is as follows:

To sum up, in fact this problem basically is to grasp the two points, one is enumerated the map corresponding to drop all of the Roman numerals, then by traversal for each map value of the Roman numerals, 2 it is to consider whether or not the Roman numerals on the right side of the greater than themselves, greater than themselves together, and smaller than oneself is presupposed, grasp the rule to problem solving.

. .

Furthermore, there are thousands of ways to solve the problem. If you have any better ideas or ideas, please let me know in the comment section. We can learn from each other and grow faster.

Well, that’s all for this episode and I’ll see you next time.

Six, the previous recommendation:

Leetcode -1. Sum of two numbers
Leetcode – 9. Palindrome

. .

Vii. Finally:

If you want to learn more, check out bug Bug’s daily Question LeetCode! Take you to brush together. One person may feel very tired and difficult to persist in brushing, but a group of people will think it is a meaningful thing to brush, urge and encourage each other, and become stronger together.

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

☘️ Be who you want to be, there is no time limit, you can start whenever you want,

🍀 You can change from now on, you can also stay the same, this thing, there are no rules to speak of, you can live the most wonderful yourself.