LeetCode第十三题：罗马数字转整数

题目来源：LeetCode第十三题

1.题目描述

罗马数字包含以下七种字符: 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

提示：

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

2.解题思路

解法一：模拟法

• 描述：通过逆序遍历整个罗马字符串，把每个罗马字符转化成对应的整数值，在遍历过程中，通过比较当前字符代表的数值和前一个字符（即右侧字符，因为是逆序遍历）代表的数值来决定是将当前数值加到总和上还是从总和中减去当前数值。
• 时间复杂度：O(n)。n是字符串的长度。
• 空间复杂度：O(1)。
• 参考代码：

java版：

class Solution {
    public int romanToInt(String s) {
        // 定义罗马数字对应的整数值
        Map<Character, Integer> romanMap = new HashMap<>();
        romanMap.put('I', 1);
        romanMap.put('V', 5);
        romanMap.put('X', 10);
        romanMap.put('L', 50);
        romanMap.put('C', 100);
        romanMap.put('D', 500);
        romanMap.put('M', 1000);

        // 用于累计结果
        int sum = 0;
        // 用于记录上一个字符代表的数值
        int prevValue = 0;
        // 从后往前遍历可以减少条件判断，例如IV，从前往后的话就需要看下一个字符来
        // 判断是当前字符是直接加上其值，还是需要从下一个字符代表的值中减去其值
        // 而从后往前判断如果当前字符代表的数值小于其右侧字符代表的数值，这意味着遇到了一个减法规则（如 IV 中的 I）
        for (int i = s.length() - 1; i >= 0; i--) {
            // 获取当前字符对应的数值
            int value = romanMap.get(s.charAt(i));
            // 如果当前的数值小于前一位的数值，说明遇到特殊的，如IV，IX，需要减去当前值
            if (value < prevValue) {
                sum -= value;
            } else {
                // 正常就直接加
                sum += value;
            }
            // 更新前一个字符代表的数值
            prevValue = value;
        }
        return sum;
    }
}

C++版：

class Solution {
public:
	int romanToInt(string s)
	{
		// 定义罗马数字对应的整数值
		unordered_map<char, int> romanMap = {
			{'I',1},
			{'V', 5},
			{'X', 10},
			{'L', 50},
			{'C', 100},
			{'D', 500},
			{'M', 1000}
		};
		// 用于累计结果
		int sum = 0;
		// 用于记录上一个字符代表的数值
		int prevValue = 0;
		// 从后往前遍历可以减少条件判断，例如IV，从前往后的话就需要看下一个字符来
		// 判断是当前字符是直接加上其值，还是需要从下一个字符代表的值中减去其值
		// 而从后往前判断如果当前字符代表的数值小于其右侧字符代表的数值，这意味着遇到了一个减法规则（如 IV 中的 I）
		for (int i = s.length() - 1; i >= 0; i--) {
			// 获取当前字符对应的数值
			int value = romanMap[s[i]];
			// 如果当前的数值小于前一位的数值，说明遇到特殊的，如IV，IX，需要减去当前值
			if (value < prevValue) {
				sum -= value;
			}
			else
			{
				// 正常就直接加
				sum += value;
			}
			// 更新前一个字符代表的数值
			prevValue = value;
		}

		return sum;
	}
};

C版：

// 将罗马数字转换为整数
int romanToInt(char* s) {
	int sum = 0; // 用于累计结果
	int prev = 0; // 用于记录上一个字符代表的数值

	// 遍历字符串
	for (int i = strlen(s) - 1; i >= 0; i--) {
		int value = 0;

		switch (s[i]) {
		case 'I': value = 1; break;
		case 'V': value = 5; break;
		case 'X': value = 10; break;
		case 'L': value = 50; break;
		case 'C': value = 100; break;
		case 'D': value = 500; break;
		case 'M': value = 1000; break;
		}

		// 如果当前值小于前一个值，说明是如IV这样的情况，应该减去当前值
		if (value < prev) {
			sum -= value;
		}
		else {
			// 否则直接加上当前值
			sum += value;
		}
		prev = value; // 更新前一个字符代表的数值
	}

	return sum;
}

解法二：查找表法

• 描述：建立一个映射表，该表不仅包含单个罗马字符对应的整数值，还包括特定的字符组合（如IV、IX等）对应的整数值。如果当前字符和下一个字符形成了一个特殊组合，则一次处理这两个字符；如果不是，再回退到处理单个字符的逻辑。
• 时间复杂度：O(n)。n是字符串长度。
• 空间复杂度：O(1)。
• 参考代码：

java版：

class Solution {
    public int romanToInt(String s) {
        // 创建一个查找表，包含所有的单字符和特殊字符组合
        Map<String, Integer> romanMap = new HashMap<>();
        romanMap.put("I", 1);
        romanMap.put("V", 5);
        romanMap.put("X", 10);
        romanMap.put("L", 50);
        romanMap.put("C", 100);
        romanMap.put("D", 500);
        romanMap.put("M", 1000);
        romanMap.put("IV", 4);
        romanMap.put("IX", 9);
        romanMap.put("XL", 40);
        romanMap.put("XC", 90);
        romanMap.put("CD", 400);
        romanMap.put("CM", 900);

        int i = 0;
        int sum = 0;

        while (i < s.length()) {
            // 如果当前位置和下一个位置的字符组合在查找表中，则直接使用该组合的值
            if (i < s.length() - 1 && romanMap.containsKey(s.substring(i, i + 2))) {
                sum += romanMap.get(s.substring(i, i + 2));
                // 跳过两个字符
                i += 2;
            } else {
                // 否则，处理单个字符
                sum += romanMap.get(s.substring(i, i + 1));
                i++;
            }
        }
        return sum;
    }
}

C++版：

class Solution {
public:
	int romanToInt(string s) {
		// 构建查找表
		unordered_map<string, int> romanMap = {
			{"I", 1}, {"V", 5}, {"X", 10}, {"L", 50},
			{"C", 100}, {"D", 500}, {"M", 1000},
			{"IV", 4}, {"IX", 9}, {"XL", 40}, {"XC", 90},
			{"CD", 400}, {"CM", 900}
		};

		int sum = 0;
		for (int i = 0; i < s.length();) {
			// 检查是否存在两个字符的特殊组合,符合就加上表中对应的值
			if (i < s.length() - 1 && romanMap.find(s.substr(i, 2)) != romanMap.end()) {
				sum += romanMap[s.substr(i, 2)];
				// 跳过两个字符
				i += 2;
			}
			else
			{
				sum += romanMap[string(1, s[i])];
				i++;
			}
		}
		return sum;
	}
};

C版：

// 定义一个结构体用于存储罗马数字字符和对应的整数值
typedef struct {
	char key[3]; // 用于存储罗马数字字符或字符组合，额外的一个字符用于字符串结束符'\0'
	int value;   // 对应的整数值
} RomanMap;

// 初始化查找表
RomanMap romanMap[] = {
	{"I", 1}, {"IV", 4}, {"V", 5}, {"IX", 9},
	{"X", 10}, {"XL", 40}, {"L", 50}, {"XC", 90},
	{"C", 100}, {"CD", 400}, {"D", 500}, {"CM", 900},
	{"M", 1000}
};
// 查找表中元素的数量
int mapSize = sizeof(romanMap) / sizeof(romanMap[0]);

int romanToInt(char* s) {
	int sum = 0;
	for (int i = 0; s[i] != '\0'; ) {
		// 尝试匹配两个字符的罗马数字组合
		int matched = 0;
		if (s[i + 1] != '\0') {
			for (int j = 0; j < mapSize; ++j) {
				if (s[i] == romanMap[j].key[0] && s[i + 1] == romanMap[j].key[1]) {
					sum += romanMap[j].value;
					i += 2;
					matched = 1;
					break;
				}
			}
		}
		// 如果没有匹配到两个字符的组合，则尝试匹配单个字符
		if (!matched) {
			for (int j = 0; j < mapSize; ++j) {
				if (s[i] == romanMap[j].key[0]) {
					sum += romanMap[j].value;
					++i;
					break;
				}
			}
		}
	}
	return sum;
}