题目描述

罗马数字包含以下七种字符: I, V, X, L,C,D 和 M。

样例

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

算法1

(模拟) $O(n)$

leetcode罗马数字.png
找规律(将一些特殊的数字框起来了,其余的都是在该基础上改了一点)
如果是反过来的话,其实大致思路也差不多,不过需要特殊处理一下
hash[s[i]] < hash[s[i + 1]]的话就说明这两个数需要做个差值

C++ 代码

class Solution {
public:
    string intToRoman(int num) {
        string reps[] = {
            "M",
            "CM","D","CD","C",
            "XC","L","XL","X",
            "IX","V","IV","I",
        };

        int values[]={
            1000,
            900,500,400,100,
            90,50,40,10,
            9,5,4,1
        };

        string res;

        for(int i = 0 ;i < 13 ; i ++)
            while(num >= values[i]){
                num -= values[i];
                res += reps[i];
            }
        return res;
    }
};

越努力越幸运