整数转罗马数字 图解题解

这道题到底在问什么

num

1994

输出

"MCMXCIV"

拆解

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

最优解：一步一步想明白

1. 3下面这排格子就是 13 个面值。看一个指针从左往右扫,能减就减、减完接着减,减不动才往右挪。盯住「剩余」和「已拼」两个数怎么变。
2. 4指针落在 1000(M)指针指向最大面值 1000(符号 M)。问:1000 能从 1994 里减掉吗?
3. 5剪 1000,拼上 M能!1000 ≤ 1994,减掉,剩余变 994,结果拼上 M。还停在 1000,看能否再减。
4. 6封存 1000,指针 → 900这次 1000 > 994,减不动。1000 这格封存变灰,指针挪到 900。
5. 7剪 900,拼上 CM900 的符号是减法形式 CM。900 ≤ 994,减掉,剩余变 94,结果变 MCM。
6. 8封存 900,指针 → 500900 减不动 94,封存,指针挪到 500。
7. 9封存 500,指针 → 400500 比 94 大,减不动,指针滑到 400。
8. 10封存 400,指针 → 100400 也比 94 大,继续滑到 100。
9. 11封存 100,指针 → 90100 只比 94 大一点点,还是减不动,滑到 90。
10. 12剪 90,拼上 XC90 的符号是 XC。90 ≤ 94,减掉,剩余只剩 4,结果变 MCMXC。
11. 13封存 90,指针 → 5090 减不动 4,封存,指针挪到 50。
12. 14封存 50,指针 → 4050 比 4 大,滑到 40。
13. 15封存 40,指针 → 1040 也比 4 大,滑到 10。
14. 16封存 10,指针 → 910 比 4 大,滑到 9。
15. 17封存 9,指针 → 59 还是比 4 大,滑到 5。
16. 18封存 5,指针 → 45 比 4 大一点,滑到 4(符号 IV)——终于来到能减的面值。
17. 19剪 4,拼上 IV4 的符号是减法形式 IV。4 ≤ 4,减掉,剩余归 0!结果拼成 MCMXCIV。
18. 20MCMXCIV ✓剩余到 0,结束。绿色的 4 个面值(M、CM、XC、IV)就是用到的,按顺序拼起来正是答案 MCMXCIV。
19. 21指针落在 1000(M)换个数 3000 再走一遍,这次专看雷区里说的同一面值连减。指针还是停在最大面值 1000(M)。
20. 22剪 1000,拼上 M1000 ≤ 3000,减掉,剩余变 2000,结果拼上 M。注意指针没右移——还在 1000 上,看还能不能再减。
21. 23再剪 1000,拼上 M还能减!1000 ≤ 2000,再减一次,剩余 1000,结果变 MM。同一格 1000 被 while 反复用——这就是「连减」。
22. 24三剪 1000,剩余归 0第 3 次:1000 ≤ 1000,减掉,剩余归 0!结果 MMM。后面的面值全用不上(变灰)。一个 while 在同一面值上连减三次,3000 就这么拼出来——这正是雷区②要的写法。
23. 25关键魔法在面值表:把 CM(900)、CD(400)、XC(90)、XL(40)、IX(9)、IV(4) 这 6 个减法形式也当成「面值」塞进表里,贪心就再不用判断何时该用减法写法。
24. 29rem=4 只能用 1 → IIII ✗假如面值表漏掉了 4(IV),轮到剩余 4 时只剩面值 1 可用,连减四次写出 IIII——这正是减法形式必须进表的原因。

⚠️ 容易写错的地方

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

class Solution:
    def intToRoman(self, num):
        vals = [1000,900,500,400,100,90,50,40,10,9,5,4,1]
        syms = ["M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"]
        res = []
        for i in range(len(vals)):
            while num >= vals[i]:        # 能减就一直减
                num -= vals[i]
                res.append(syms[i])
        return "".join(res)

class Solution {
public:
    string intToRoman(int num) {
        int vals[] = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
        string syms[] = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
        string res;
        for (int i = 0; i < 13; i++) {
            while (num >= vals[i]) { num -= vals[i]; res += syms[i]; }
        }
        return res;
    }
};

class Solution {
    public String intToRoman(int num) {
        int[] vals = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
        String[] syms = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < 13; i++) {
            while (num >= vals[i]) { num -= vals[i]; res.append(syms[i]); }
        }
        return res.toString();
    }
}

复杂度

面试官可能追问