罗马数字转整数 图解题解

这道题到底在问什么

s

"MCMXCIV"

输出

1994

拆解

M(1000)+CM(900)+XC(90)+IV(4)

最优解：一步一步想明白

1. 3切块法要先想清楚「哪两个字符要合并」,边界一多就容易写错。有没有不用提前切块的办法?
2. 4不用切块!逐个字符看:cur < 右邻 → 减,否则 → 加。比如 IV 的 I(1) 比右边 V(5) 小,就减 1;V 没有右边,就加 5。
3. 5盯住三件事:cur 指针在哪、当前符号和右邻谁大、total 怎么变。绿色 visited = 已处理完的格子。
4. 6cur 落在第0格 M(1000)cur 停在第 0 格 M(1000)。规则:要看它和右边那格谁大,才知道该加还是减。
5. 7右邻 = 第1格 C(100)右边那格(变暗的)是 C(100)。把这两个数拎出来比:M 1000、C 100。
6. 8cur=M,右邻=C,1000>100右邻是 C(100)。1000 > 100,不是减法形式 → 正常加。total 从 0 变 1000。
7. 9M 已处理,cur → 第1格 C第 0 格 M 处理完变绿,cur 右移到第 1 格 C(100)。又要和右邻比了。
8. 10cur=C,右邻=M,100<1000右邻是 M(1000)。100 < 1000 → 这个 C 是减法形式 CM 的前半,要减!total 反而从 1000 降到 900。这正是减法的精髓。
9. 11C 已处理,cur → 第2格 M前两格 M、C 都处理完了(绿)。cur 来到第 2 格 M(1000),继续和右邻比。
10. 12cur=M,右邻=X,1000>10右邻 X(10)。1000 > 10 → 正常加。total 升到 1900。这个 M 就是 CM 里的「大」那一半,加回来了。
11. 13cur → 第3格 Xcur 移到第 3 格 X(10)。又是熟悉的动作:看右边。
12. 14cur=X,右邻=C,10<100右邻 C(100)。10 < 100 → X 是减法形式 XC 的前半,减!total 降到 1890。
13. 15cur → 第4格 Ccur 到第 4 格 C(100)。注意同样是 C,这次右边不一样,结果就可能不同——继续比。
14. 16cur=C,右邻=I,100>1右邻 I(1)。100 > 1 → 这个 C 正常加(它是 XC 里的大半)。total 升到 1990。
15. 17cur → 第5格 Icur 到第 5 格 I(1),只剩最后两格了。还是先看右边。
16. 18cur=I,右邻=V,1<5右邻 V(5)。1 < 5 → I 是减法形式 IV 的前半,减!total 降到 1989。
17. 19cur → 第6格 V,无右邻最后一格 V(5),右边没有字符了。没有右邻就不可能是减法形式 → 直接加。total = 1994!
18. 20MCMXCIV → 1994 ✓7 格全部走完。三处「小在大左边」的格子(C、X、I)做了减,其余做加,合起来正好 MCMXCIV = 1994。整条规则就这么简单。
19. 21只有 2 格:I、X换个短例子 IX 巩固减法。cur 在第 0 格 I,右邻是 X。
20. 22右邻 = X(10)把右邻 X(10) 拎出来(变暗格)和 I(1) 比。明显 X 更大。
21. 231<10 → 减1 < 10 → I 减掉,total 先变成 −1。别慌,下一步 X 加回来。
22. 24cur → X,无右邻 → 加X 没有右邻 → 加 10,total = −1 + 10 = 9。可见「先减小的、再加大的」自然就把 IX 算成 9,完全不用提前识别 IX 是个整体。
23. 25比如 IV:先加 I(=1),到 V 时发现上一个 I 比 V 小,于是 total = 1 + 5 − 2×1 = 4。和「向右看」是同一回事,代码里两种都常见,理解一种即可。
24. 29把 IV 全加 → 6 ✗假如不做减法判断,IV 会被算成 1+5=6。正因为 I 在比它大的 V 左边要减,答案才是 4。这就是减法判断不能省的原因。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def romanToInt(self, s):
        d = {'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
        total = 0
        n = len(s)
        for i in range(n):
            if i + 1 < n and d[s[i]] < d[s[i+1]]:   # 小在大左边
                total -= d[s[i]]                     # 减
            else:
                total += d[s[i]]                     # 加
        return total

class Solution {
public:
    int romanToInt(string s) {
        unordered_map<char,int> d = {
            {'I',1},{'V',5},{'X',10},{'L',50},
            {'C',100},{'D',500},{'M',1000}};
        int total = 0, n = s.size();
        for (int i = 0; i < n; i++) {
            if (i + 1 < n && d[s[i]] < d[s[i+1]]) total -= d[s[i]];
            else total += d[s[i]];
        }
        return total;
    }
};

class Solution {
    public int romanToInt(String s) {
        Map<Character,Integer> d = new HashMap<>();
        d.put('I',1); d.put('V',5); d.put('X',10); d.put('L',50);
        d.put('C',100); d.put('D',500); d.put('M',1000);
        int total = 0, n = s.length();
        for (int i = 0; i < n; i++) {
            if (i + 1 < n && d.get(s.charAt(i)) < d.get(s.charAt(i+1)))
                total -= d.get(s.charAt(i));
            else
                total += d.get(s.charAt(i));
        }
        return total;
    }
}

复杂度

面试官可能追问