leetcode 精选100题（LeetCode力扣官方题解）(1)

力扣 13. 罗马数字转整数 （点击文末阅读原文查看题目）

题目描述

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

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

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

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。

同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。

示例 1：

输入: "III" 输出: 3

示例 2：

输入: "IV" 输出: 4

示例 3：

输入: "IX" 输出: 9

示例 4：

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

示例 5：

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

提示：

解决方案

方法一：模拟

思路

通常情况下，罗马数字中小的数字在大的数字的右边。若输入的字符串满足该情况，那么可以将每个字符视作一个单独的值，累加每个字符对应的数值即可。

例如 XXVII 可视作 X X V I I = 10 10 5 1 1 = 27。

若存在小的数字在大的数字的左边的情况，根据规则需要减去小的数字。对于这种情况，我们也可以将每个字符视作一个单独的值，若一个数字右侧的数字比它大，则将该数字的符号取反。

例如 XIV 可视作 X - I V = 10 - 1 5 = 14

C

class Solution { private: unordered_map<char, int> symbolValues = { {'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; } } return ans; } };

Java

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; } } return ans; } }

C#

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; } } return ans; } }

Golang

var symbolValues = map[byte]int{'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000} func romanToInt(s string) (ans int) { n := len(s) for i := range s { value := symbolValues[s[i]] if i < n-1 && value < symbolValues[s[i 1]] { ans -= value } else { ans = value } } return }

JavaScript

var romanToInt = function(s) { const symbolValues = new Map(); symbolValues.set('I', 1); symbolValues.set('V', 5); symbolValues.set('X', 10); symbolValues.set('L', 50); symbolValues.set('C', 100); symbolValues.set('D', 500); symbolValues.set('M', 1000); let ans = 0; const n = s.length; for (let i = 0; i < n; i) { const value = symbolValues.get(s[i]); if (i < n - 1 && value < symbolValues.get(s[i 1])) { ans -= value; } else { ans = value; } } return ans; };

Python3

class Solution: SYMBOL_VALUES = { 'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000, } def romanToInt(self, s: str) -> int: ans = 0 n = len(s) for i, ch in enumerate(s): value = Solution.SYMBOL_VALUES[ch] if i < n - 1 and value < Solution.SYMBOL_VALUES[s[i 1]]: ans -= value else: ans = value returnans

C

int romanToInt(char* s) { int symbolValues[26]; symbolValues['I' - 'A'] = 1; symbolValues['V' - 'A'] = 5; symbolValues['X' - 'A'] = 10; symbolValues['L' - 'A'] = 50; symbolValues['C' - 'A'] = 100; symbolValues['D' - 'A'] = 500; symbolValues['M' - 'A'] = 1000; int ans = 0; int n = strlen(s); for (int i = 0; i < n; i) { int value = symbolValues[s[i] - 'A']; if (i < n - 1 && value < symbolValues[s[i 1] - 'A']) { ans -= value; } else { ans = value; } } return ans; }

复杂度分析

本文作者：力扣

声明：本文归“力扣”版权所有，如需转载请联系。

,