力扣00013.罗马数字转整数

发表于 分类于 阅读次数： 本文字数： 2.2k 阅读时长 ≈ 8 分钟
罗马数字转整数、哈希表、数学、字符串、简单

题目描述

罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。

字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000

例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

  • I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
  • X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
  • C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个罗马数字，将其转换成整数。

示例 1：

输入: s = “III”
输出: 3

示例 2：

输入: s = “IV”
输出: 4

示例 3:

输入: s = “IX”
输出: 9

示例 4:

输入: s = “LVIII”
输出: 58
解释: L = 50, V= 5, III = 3.

示例 5:

输入: s = “MCMXCIV”
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

提示：

  • 1 <= s.length <= 15
  • s 仅含字符 (‘I’, ‘V’, ‘X’, ‘L’, ‘C’, ‘D’, ‘M’)
  • 题目数据保证 s 是一个有效的罗马数字，且表示整数在范围 [1, 3999] 内
  • 题目所给测试用例皆符合罗马数字书写规则，不会出现跨位等情况。
  • IL 和 IM 这样的例子并不符合题目要求，49 应该写作 XLIX，999 应该写作 CMXCIX 。

解决方法

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int romanToInt(string s) {
        unordered_map<char, int> roman_values = {
            {'I', 1}, {'V', 5}, {'X', 10}, {'L', 50},
            {'C', 100}, {'D', 500}, {'M', 1000}
        };
        int total = 0;
        for (int i = 0; i < s.length(); ++i) {
            if (i + 1 < s.length() && roman_values[s[i]] < roman_values[s[i + 1]]) {
                total += roman_values[s[i + 1]] - roman_values[s[i]];
                ++i;
            } else {
                total += roman_values[s[i]];
            }
        }
        return total;
    }
};

结果

执行用时 : 12 ms, 击败 63.8% 使用 C++ 的用户

内存消耗 : 8.18 MB, 击败 62.73% 使用 C++ 的用户

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.HashMap;
class Solution {
    public int romanToInt(String s) {
        HashMap<Character, Integer> romanValues = new HashMap<>();
        romanValues.put('I', 1);
        romanValues.put('V', 5);
        romanValues.put('X', 10);
        romanValues.put('L', 50);
        romanValues.put('C', 100);
        romanValues.put('D', 500);
        romanValues.put('M', 1000);
        int total = 0;
        for (int i = 0; i < s.length(); ++i) {
            if (i + 1 < s.length() && romanValues.get(s.charAt(i)) < romanValues.get(s.charAt(i + 1))) {
                total += romanValues.get(s.charAt(i + 1)) - romanValues.get(s.charAt(i));
                ++i;
            } else {
                total += romanValues.get(s.charAt(i));
            }
        }
        return total;
    }
}

结果

执行用时 : 6 ms, 击败 18.77% 使用 Java 的用户

内存消耗 : 43.35 MB, 击败 17.83% 使用 Java 的用户

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def romanToInt(self, s):
        roman_values = {
            'I': 1, 'V': 5, 'X': 10, 'L': 50,
            'C': 100, 'D': 500, 'M': 1000
        }
        total = 0
        i = 0
        while i < len(s):
            if i + 1 < len(s) and roman_values[s[i]] < roman_values[s[i + 1]]:
                total += roman_values[s[i + 1]] - roman_values[s[i]]
                i += 2
            else:
                total += roman_values[s[i]]
                i += 1
        return total

结果

执行用时 : 44 ms, 击败 91.49% 使用 Python 的用户

内存消耗 : 12.98 MB, 击败 60.24% 使用 Python 的用户

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def romanToInt(self, s: str) -> int:
        roman_values = {
            'I': 1, 'V': 5, 'X': 10, 'L': 50,
            'C': 100, 'D': 500, 'M': 1000
        }
        total = 0
        i = 0
        while i < len(s):
            if i + 1 < len(s) and roman_values[s[i]] < roman_values[s[i + 1]]:
                total += roman_values[s[i + 1]] - roman_values[s[i]]
                i += 2
            else:
                total += roman_values[s[i]]
                i += 1
        return total

结果

执行用时 : 56 ms, 击败 60.20% 使用 Python3 的用户

内存消耗 : 17.10 MB, 击败 5.04% 使用 Python3 的用户

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int value(char c) {
    switch(c) {
        case 'I': return 1;
        case 'V': return 5;
        case 'X': return 10;
        case 'L': return 50;
        case 'C': return 100;
        case 'D': return 500;
        case 'M': return 1000;
        default: return 0;
    }
}
int romanToInt(char* s) {
    int result = 0;
    for (int i = 0; s[i] != '\0'; i++) {
        int current = value(s[i]);
        int next = value(s[i + 1]);
        if (current < next) {
            result += (next - current);
            i++;
        } else {
            result += current;
        }
    }
    return result;
}

结果

执行用时 : 8 ms, 击败 58.83% 使用 C 的用户

内存消耗 : 6.36 MB, 击败 87.77% 使用 C 的用户

C#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    public int RomanToInt(string s) {
        Dictionary<char, int> romanValues = new Dictionary<char, int>() {
            {'I', 1}, {'V', 5}, {'X', 10}, {'L', 50},
            {'C', 100}, {'D', 500}, {'M', 1000}
        };
        int total = 0;
        for (int i = 0; i < s.Length; i++) {
            if (i + 1 < s.Length && romanValues[s[i]] < romanValues[s[i + 1]]) {
                total += romanValues[s[i + 1]] - romanValues[s[i]];
                i++;
            } else {
                total += romanValues[s[i]];
            }
        }
        return total;
    }
}

结果

执行用时 : 60 ms, 击败 85.78% 使用 C# 的用户

内存消耗 : 47.64 MB, 击败 18.79% 使用 C# 的用户

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function(s) {
    const romanValues = {
        'I': 1, 'V': 5, 'X': 10, 'L': 50,
        'C': 100, 'D': 500, 'M': 1000
    };
    let total = 0;
    for (let i = 0; i < s.length; i++) {
        if (i + 1 < s.length && romanValues[s[i]] < romanValues[s[i + 1]]) {
            total += romanValues[s[i + 1]] - romanValues[s[i]];
            i++;
        } else {
            total += romanValues[s[i]];
        }
    }
    return total;
};

结果

执行用时 : 116 ms, 击败 63.20% 使用 JavaScript 的用户

内存消耗 : 53.13 MB, 击败 7.86% 使用 JavaScript 的用户

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function romanToInt(s: string): number {
    const romanValues: { [key: string]: number } = {
        'I': 1, 'V': 5, 'X': 10, 'L': 50,
        'C': 100, 'D': 500, 'M': 1000
    };
    let total = 0;
    for (let i = 0; i < s.length; i++) {
        if (i + 1 < s.length && romanValues[s[i]] < romanValues[s[i + 1]]) {
            total += romanValues[s[i + 1]] - romanValues[s[i]];
            i++;
        } else {
            total += romanValues[s[i]];
        }
    }
    return total;
}

结果

执行用时 : 124 ms, 击败 44.44% 使用 TypeScript 的用户

内存消耗 : 53.39 MB, 击败 11.57% 使用 TypeScript 的用户

PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {

    /**
     * @param String $s
     * @return Integer
     */
    function romanToInt($s) {
        $romanValues = [
            'I' => 1, 'V' => 5, 'X' => 10, 'L' => 50,
            'C' => 100, 'D' => 500, 'M' => 1000
        ];
        $total = 0;
        for ($i = 0; $i < strlen($s); $i++) {
            if ($i + 1 < strlen($s) && $romanValues[$s[$i]] < $romanValues[$s[$i + 1]]) {
                $total += $romanValues[$s[$i + 1]] - $romanValues[$s[$i]];
                $i++;
            } else {
                $total += $romanValues[$s[$i]];
            }
        }
        return $total;
    }
}

结果

执行用时 : 16 ms, 击败 72.29% 使用 PHP 的用户

内存消耗 : 19.67 MB, 击败 6.03% 使用 PHP 的用户

Swift

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    func romanToInt(_ s: String) -> Int {
        let romanValues: [Character: Int] = [
            "I": 1, "V": 5, "X": 10, "L": 50,
            "C": 100, "D": 500, "M": 1000
        ]
        var total = 0
        var i = s.startIndex
        while i < s.endIndex {
            let current = s[i]
            let nextIndex = s.index(after: i)
            if nextIndex < s.endIndex {
                let next = s[nextIndex]
                if romanValues[current]! < romanValues[next]! {
                    total += romanValues[next]! - romanValues[current]!
                    i = s.index(after: nextIndex)
                    continue
                }
            }
            total += romanValues[current]!
            i = s.index(after: i)
        }
        return total
    }
}

结果

执行用时 : 24 ms, 击败 32.26% 使用 Swift 的用户

内存消耗 : 15.66 MB, 击败 6.45% 使用 Swift 的用户

Kotlin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    fun romanToInt(s: String): Int {
        val romanValues = hashMapOf(
            'I' to 1, 'V' to 5, 'X' to 10, 'L' to 50,
            'C' to 100, 'D' to 500, 'M' to 1000
        )
        var total = 0
        var i = 0
        while (i < s.length) {
            if (i + 1 < s.length && romanValues[s[i]]!! < romanValues[s[i + 1]]!!) {
                total += romanValues[s[i + 1]]!! - romanValues[s[i]]!!
                i += 2
            } else {
                total += romanValues[s[i]]!!
                i++
            }
        }
        return total
    }
}

结果

执行用时 : 224 ms, 击败 40.00% 使用 Kotlin 的用户

内存消耗 : 36.78 MB, 击败 40.00% 使用 Kotlin 的用户

Dart

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
  int romanToInt(String s) {
    Map<String, int> romanValues = {
      'I': 1, 'V': 5, 'X': 10, 'L': 50,
      'C': 100, 'D': 500, 'M': 1000
    };
    int total = 0;
    for (int i = 0; i < s.length; i++) {
      if (i + 1 < s.length &&
          romanValues[s[i]]! < romanValues[s[i + 1]]!) {
        total += romanValues[s[i + 1]]! - romanValues[s[i]]!;
        i++;
      } else {
        total += romanValues[s[i]]!;
      }
    }
    return total;
  }
}

结果

执行用时 : 380 ms, 击败 20.00% 使用 Dart 的用户

内存消耗 : 148.83 MB, 击败 100.00% 使用 Dart 的用户

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func romanToInt(s string) int {
    romanValues := map[byte]int{
        'I': 1, 'V': 5, 'X': 10, 'L': 50,
        'C': 100, 'D': 500, 'M': 1000,
    }
    total := 0
    for i := 0; i < len(s); i++ {
        if i+1 < len(s) && romanValues[s[i]] < romanValues[s[i+1]] {
            total += romanValues[s[i+1]] - romanValues[s[i]]
            i++
        } else {
            total += romanValues[s[i]]
        }
    }
    return total
}

结果

执行用时 : 8 ms, 击败 52.05% 使用 Go 的用户

内存消耗 : 2.64 MB, 击败 78.89% 使用 Go 的用户

Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# @param {String} s
# @return {Integer}
def roman_to_int(s)
    roman_values = {
        'I' => 1, 'V' => 5, 'X' => 10, 'L' => 50,
        'C' => 100, 'D' => 500, 'M' => 1000
    }
    total = 0
    i = 0
    while i < s.length
        if i + 1 < s.length && roman_values[s[i]] < roman_values[s[i + 1]]
            total += roman_values[s[i + 1]] - roman_values[s[i]]
            i += 2
        else
            total += roman_values[s[i]]
            i += 1
        end
    end
    return total
end

结果

执行用时 : 68 ms, 击败 100.00% 使用 Ruby 的用户

内存消耗 : 206.81 MB, 击败 16.67% 使用 Ruby 的用户

Scala

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
object Solution {
  def romanToInt(s: String): Int = {
    val romanValues = Map(
      'I' -> 1, 'V' -> 5, 'X' -> 10, 'L' -> 50,
      'C' -> 100, 'D' -> 500, 'M' -> 1000
    )
    var total = 0
    var i = 0
    while (i < s.length) {
      if (i + 1 < s.length && romanValues(s(i)) < romanValues(s(i + 1))) {
        total += romanValues(s(i + 1)) - romanValues(s(i))
        i += 2
      } else {
        total += romanValues(s(i))
        i += 1
      }
    }
    total
  }
}

结果

执行用时 : 540 ms, 击败 87.50% 使用 Scala 的用户

内存消耗 : 54.98 MB, 击败 62.50% 使用 Scala 的用户

Rust

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
use std::collections::HashMap;

impl Solution {
    pub fn roman_to_int(s: String) -> i32 {
        let mut roman_values: HashMap<char, i32> = HashMap::new();
        roman_values.insert('I', 1);
        roman_values.insert('V', 5);
        roman_values.insert('X', 10);
        roman_values.insert('L', 50);
        roman_values.insert('C', 100);
        roman_values.insert('D', 500);
        roman_values.insert('M', 1000);
        let mut total = 0;
        let mut prev = 0;
        for c in s.chars() {
            let curr = roman_values[&c];
            total += curr;
            if curr > prev {
                total -= 2 * prev;
            }
            prev = curr;
        }
        total
    }
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 Rust 的用户

内存消耗 : 2.20 MB, 击败 17.91% 使用 Rust 的用户

Racket

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
(define (roman-to-int s)
  (define roman-values
    '((#\I . 1) (#\V . 5) (#\X . 10) (#\L . 50)
      (#\C . 100) (#\D . 500) (#\M . 1000)))
  (define (get-value c)
    (cdr (assoc c roman-values)))
  (let loop ((chars (string->list s))
             (result 0))
    (cond
      ((null? chars) result)
      ((= (length chars) 1) (+ result (get-value (car chars))))
      (else
       (let ((current (get-value (car chars)))
             (next (get-value (cadr chars))))
         (if (< current next)
             (loop (cddr chars) (+ result (- next current)))
             (loop (cdr chars) (+ result current))))))))

结果

执行用时 : 216 ms, 击败 100.00% 使用 Racket 的用户

内存消耗 : 97.95 MB, 击败 100.00% 使用 Racket 的用户

Erlang

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Erlang 的用户

内存消耗 : MB, 击败 % 使用 Erlang 的用户

Elixir

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Elixir 的用户

内存消耗 : MB, 击败 % 使用 Elixir 的用户