0013. Roman to Integer

题目信息

题号:
  1. 罗马数字转整数

难度:

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++ 实现

#include <string>

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<int>(s.size())) {
            const int current = value(s[index]);
            if (index + 1 < static_cast<int>(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<int>(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)。 字符到数值的映射只有七种分支,单次查询为常数时间。