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

}