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

📢 preface

  • 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻
  • 🌲 punch in an algorithm every day, which is not only a learning process, but also a sharing process 😜
  • 🌲 tip: the programming languages used in this column are C# and Java
  • 🌲 to maintain a state of learning every day, let us work together to become a god of algorithms 🧐!
  • 🌲 today is the ninth day 🎈!
  • 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻

🌲 Example of original problem

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

Character value I1
V             5
X             10
L             50
C             100
D             500
M             1000
Copy 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 a Roman numeral, convert it to an integer. Make sure the input is in the range of 1 to 3999.

The sample1Input:"III"Output:3
Copy the code
The sample2Input:"IV"Output:4
Copy the code
The sample3Input:"IX"Output:9
Copy the code
The sample4Input:"LVIII"Output:58Explanation: L =50, V= 5, III = 3.
Copy the code
The sample5Input:"MCMXCIV"Output:1994Explanation: M =1000, CM = 900, XC = 90, IV = 4.
Copy the code

Tip:

  • 1 <= s.length <= 15
  • S contains only characters (‘I’, ‘V’, ‘X’, ‘L’, ‘C’, ‘D’, ‘M’)
  • The data guarantees that s is a valid Roman numeral and represents an integer within the range [1, 3999]
  • All test cases are in accordance with the Roman numerals writing rules, and there will be no cross-position.
  • Examples like IL and IM don’t fit the question, 49 should be XLIX, 999 should be CMXCIX.
  • For detailed rules for writing Roman numerals, see Roman numerals – Mathematics.

🌻C# method 1: simulation

Thinking analytical

  • First of all, we can see that the simplest idea is to count each Roman character as a fixed value

  • For example, XVII can be seen as X+V+I+I= X+X+V+I+I=10+5+1+1=17.

  • But there’s a problem here, which is that Roman numbers tend to have smaller numbers to the left of larger numbers

  • That’s the six special cases in the title!

  • So let’s make a judgment call about when that happens

  • If a smaller number is to the left of a larger number, the rule requires subtracting the smaller number.

  • In this case, we can also treat each character as a single value and reverse the sign of a number if the number to the right is larger than it is.

  • For example, XIV can be taken as X−II+V=10−2+5=13.

code

public class Solution {
    Dictionary<char.int> symbolValues = new Dictionary<char.int> {{'I'.1},
        {'V'.5},
        {'X'.10},
        {'L'.50},
        {'C'.100},
        {'D'.500},
        {'M'.1000}};public int RomanToInt(string s) {
        int ans = 0;
        int n = s.Length;
        for (int i = 0; i < n; ++i) {
            int value = symbolValues[s[i]];
            if (i < n - 1 && value < symbolValues[s[i + 1]]) {
                ans -= value;
            } else {
                ans += value; }}returnans; }}Copy the code

The execution result

By execution time:72Ms, in all CBeat 99.86% of users in # commitMemory consumption:25.6MB, in all C# beat 65.70% of users in submission
Copy the code

Complexity analysis

Time complexity: O(n), where n is the length of string S. Space complexity: O(1)
Copy the code

🌻C# method two: substitution method

  • The above solution is the most simple one, I see the solution of the time found a big man’s idea is more strange, let’s have a look

  • We use C#’s string substitution method to make a single new character and assign it to each of the six possible situations in the key title!

  • Simply put, it is to replace the six special cases IV, IX, XL, XC, CD, CM with our custom characters!

  • Take a look at the code and you’ll see!

Code:

public class Solution {
    public int RomanToInt(string s) {
        s=s.Replace("IV"."Y");
        s=s.Replace("IX"."T");
        s=s.Replace("XL"."U");
        s=s.Replace("XC"."R");
        s=s.Replace("CD"."O");
        s=s.Replace("CM"."W");
        int sum=0;
        int i=0;
        for (i=0; i<s.Length; i++){switch (s[i]){
                case 'M':
                    sum+=1000;
                    break;
                case 'W':
                    sum+=900;
                    break;
                case 'D':
                    sum+=500;
                    break;
                case 'O':
                    sum+=400;
                    break;    
                case 'C':
                    sum+=100;
                    break;
                case 'R':
                    sum+=90;
                    break;
                case 'L':
                    sum+=50;
                    break;
                case 'U':
                    sum+=40;
                    break;
                case 'X':
                    sum+=10;
                    break;
                case 'T':
                    sum+=9;
                    break;
                case 'V':
                    sum+=5;
                    break;
                case 'Y':
                    sum+=4;
                    break;
                case 'I':
                    sum+=1;
                    break; }}returnsum; }} Link: HTTPS://leetcode-cn.com/problems/roman-to-integer/solution/c-ti-huan-fa-jia-swtich-by-zapquiyou/
Copy the code

The execution result

By execution time:80Ms, in all CBeat 99.96% of users in # submissionsMemory consumption:25.4MB, in all CDefeated 94.33% of users in # submit
Copy the code

Complexity analysis

Time: O(n) Space: O(1)
Copy the code

🌻Java method: emulation

Their thinking

This solution with C# the first method an idea, but the code is slightly different!

code

class Solution {
    Map<Character, Integer> symbolValues = 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;
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            int value = symbolValues.get(s.charAt(i));
            if (i < n - 1 && value < symbolValues.get(s.charAt(i + 1))) {
                ans -= value;
            } else{ ans += value; }}returnans; }}Copy the code

The execution result

By execution time:6Ms, beat out all Java commits66.37% user memory consumption:39MB, beat out all Java commits19.37% of the userCopy the code

Complexity analysis

Time: O(n) Space: O(1)
Copy the code

💬 summary

  • Today is the ninth day of buckle algorithm clocking!
  • This paper uses C# and Java programming languages to solve the problem
  • Sometimes some methods are written by the god of reference force buckle, but also while learning and sharing, thanks again to the algorithm masters
  • That’s the end of today’s algorithm sharing, see you tomorrow!