LeetCode_12: Integer to Roman

# 引言

题目链接：https://leetcode.com/problems/integer-to-roman/description/

# 题目大意

输入一个整型数字, 将这个数字转换为罗马数字

有如下约定

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.

• Example

Input: 3
Output: "III"

Input: 4
Output: "IV"

Input: 9
Output: "IX"

Input: 58
Output: "LVIII"
Explanation: C = 100, L = 50, XXX = 30 and III = 3.

Input: 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

# 题解

# 一句话题解

一个简单模拟, 按照罗马数字的构造方式模拟即可(**Hint:**关于9或者4的特殊情况可以通过手动构造符号映射避免额外的判断)

# 复杂度

时间复杂度 O(n)

空间复杂度 O(n)

# AC代码

c++版本

class Solution
{
  public:
    string intToRoman(int num)
    {
        vector<pair<int, string>> romanSymbol{
            {1000, "M"}, {900, "CM"}, {500, "D"}, {400, "CD"},
            {100, "C"}, {90, "XC"}, {50, "L"}, {40, "XL"},
            {10, "X"}, {9, "IX"}, {5, "V"}, {4, "IV"}, {1, "I"}};
        vector<pair<int, string>>::const_iterator iter = romanSymbol.cbegin();
        string ans = "";
        while (num > 0 && iter != romanSymbol.cend())
        {
            if (num >= iter->first)
            {
                num -= iter->first;
                ans += iter->second;
            }
            else
            {
                ++iter;
            }
        }
        return ans;
    }
};

go版本

type roman struct {
	value  int
	symbol string
}

func intToRoman(num int) string {
	romans := []roman{
		{1000, "M"}, {900, "CM"}, {500, "D"}, {400, "CD"},
		{100, "C"}, {90, "XC"}, {50, "L"}, {40, "XL"},
		{10, "X"}, {9, "IX"}, {5, "V"}, {4, "IV"}, {1, "I"}}
	ans := ""
	index := 0
	for num > 0 {
		if num >= romans[index].value {
			num -= romans[index].value
			ans += romans[index].symbol
		} else {
			index++
		}
	}
	return ans
}