0013. Roman to Integer
======================
题目信息
--------
:题号: 0013. 罗马数字转整数
:难度: Easy
:主题: 字符串、映射、相邻关系
:原题: `LeetCode 0013 `_
:重点: 把规范罗马串拆成单符号与减法对,再把减法对展开为由右侧较大值决定的正负贡献
题目重述
--------
给定一个合法罗马数字字符串 ``s``,返回它表示的整数。
七个基本符号为 ``I=1``、``V=5``、``X=10``、``L=50``、``C=100``、``D=500``、``M=1000``。
通常符号按非增数值排列并相加;六种减法组合 ``IV``、``IX``、``XL``、``XC``、``CD``、``CM``
表示用右侧较大值减去左侧较小值。
字符串长度位于 ``[1, 15]``,只包含上述七种字符,并保证是 ``[1, 3999]`` 范围内整数的规范表示。
因此只需完成转换,不需要识别或修复 ``IC``、``VX`` 等非法写法。
自建示例
--------
* 只有加法符号:``s = "VIII"``,计算为 ``5 + 1 + 1 + 1``,返回 ``8``;
* 单个减法对:``s = "IX"``,计算为 ``10 - 1``,返回 ``9``;
* 多个减法对:``s = "CDXLIV"``,计算为 ``400 + 40 + 4``,返回 ``444``;
* 混合结构:``s = "MCMXLIV"``,计算为 ``1000 + 900 + 40 + 4``,返回 ``1944``;
* 单个符号:``s = "I"``,返回 ``1``。
C++ 实现
--------
.. code-block:: cpp
#include
class Solution {
private:
int value(char symbol) {
switch (symbol) {
case 'I': return 1;
case 'V': return 5;
case 'X': return 10;
case 'L': return 50;
case 'C': return 100;
case 'D': return 500;
default: return 1000;
}
}
int parseTokens(const std::string& s) {
int result = 0;
int index = 0;
while (index < static_cast(s.size())) {
const int current = value(s[index]);
if (index + 1 < static_cast(s.size())) {
const int next = value(s[index + 1]);
if (current < next) {
result += next - current;
index += 2;
continue;
}
}
result += current;
++index;
}
return result;
}
int scanFromRight(const std::string& s) {
int result = 0;
int rightMaximum = 0;
for (int index = static_cast(s.size()) - 1; index >= 0; --index) {
const int current = value(s[index]);
if (current < rightMaximum) {
result -= current;
} else {
result += current;
rightMaximum = current;
}
}
return result;
}
public:
int romanToInt(std::string s) {
return scanFromRight(s);
}
};
题解
----
直接相加的缺口
~~~~~~~~~~~~~~
若把每个符号都作为正数相加,``VI`` 会正确得到 ``6``,``IV`` 却会错误得到 ``6``。区别不在符号本身,
而在较小符号是否位于较大符号左侧。
规范罗马串可以从左到右拆成两类单位:
* 一个普通符号,例如 ``M``、``D``、``III`` 中的每个 ``I``;
* 一个允许的减法对,例如 ``CM``、``XL``、``IV``。
题目保证输入合法,所以只要相邻值出现上升,当前两个字符就必然构成允许的减法对。
按单位解析
~~~~~~~~~~
``parseTokens`` 从左向右读取当前符号。若下一符号更大,就把两者作为一个减法单位,加入
``next - current`` 并前进两格;否则加入当前值并前进一格。
以 ``MCMXLIV`` 为例,它被依次拆为:
``M | CM | XL | IV``
各单位贡献 ``1000``、``900``、``40``、``4``,总和为 ``1944``。每个字符只属于一个单位,不会遗漏或
重复计算。
带符号贡献
~~~~~~~~~~
减法对 ``XY`` 的数值可以展开为:
``value(Y) - value(X) = -value(X) + value(Y)``。
因此不必真的把两个字符组合后再处理。只要知道当前较小符号的右侧存在更大值,就可以把当前值减去;其余符号
全部加上。
规范表示按十进制位从高到低排列,每个位置内部只有减法对会出现数值上升。于是从右向左扫描时:
* 当前值小于右侧已见最大值,它就是某个减法对的左半部分,应减去;
* 当前值不小于右侧最大值,它属于普通加法单位,应加上,并成为新的右侧最大值。
状态不变量
~~~~~~~~~~
``scanFromRight`` 每轮开始时维护两个事实:
* ``result`` 已经等于右侧处理区域的正确数值贡献;
* ``rightMaximum`` 是该区域出现过的最大符号值。
加入当前字符时,``current < rightMaximum`` 恰好表示它位于更大单位左侧。减去当前值后,右侧区域的解释保持
正确;否则当前值作为普通单位加入,并更新最大值。循环结束后,整个字符串的每个字符都已经获得唯一的正负
贡献。
对 ``MCMXLIV``,从右向左得到贡献序列:
``+V -I +L -X +M -C +M``
即 ``5 - 1 + 50 - 10 + 1000 - 100 + 1000 = 1944``。
代码演进
~~~~~~~~
``parseTokens`` 直接按照题目规则识别单符号与减法对,结构最接近罗马数字的书写定义。
``scanFromRight`` 把减法对展开为两个带符号贡献。相邻字符成对消费、索引跳两格和末尾边界判断全部消失,只需
维护右侧最大值。
公开入口采用 ``scanFromRight``。它与按单位解析具有相同的线性时间,状态更少,并能用一个循环统一处理所有
字符。
复杂度分析
~~~~~~~~~~
设字符串长度为 ``n``。两种方法都只访问每个字符常数次,时间复杂度为 ``O(n)``,工作空间为 ``O(1)``。
字符到数值的映射只有七种分支,单次查询为常数时间。