LeetCode 12/13 罗马数字与整型互转（哈希，贪心）

Michael阿明

发布于 2020-07-13 16:31:32

4350

发布于 2020-07-13 16:31:32

1. 罗马数字转整型

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

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

例如，罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。

示例 1:
输入: "III"
输出: 3

示例 2:
输入: "IV"
输出: 4

示例 3:
输入: "IX"
输出: 9

示例 4:
输入: "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.

示例 5:
输入: "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/roman-to-integer 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题

如果第连续的2个字符在哈希表中，则减去前一个字符的数值

class Solution {
public:
    int romanToInt(string s) {
        unordered_map<string,int> m;
        m["I"]=1, m["V"]=5,m["X"]=10,m["L"]=50,m["C"]=100,m["D"]=500,m["M"]=1000;
        m["IV"]=4,m["IX"]=9,m["XL"]=40,m["XC"]=90,m["CD"]=400,m["CM"]=900;
        int sum = m[string(1,s[0])];
        string str;
        for(int i = 1; i < s.size(); ++i)
        {
            str = string(s,i-1,2);
            if(m.find(str) != m.end())//连续的两个在表中
                sum += m[str]-m[string(1,s[i-1])];//减去前一个字符的数值
            else
                sum += m[string(1,s[i])];
        }
        return sum;
    }
};

2. 整数转罗马数字

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

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

例如，罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内。

示例 1:
输入: 3
输出: "III"

示例 2:
输入: 4
输出: "IV"

示例 3:
输入: 9
输出: "IX"

示例 4:
输入: 58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.

示例 5:
输入: 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/integer-to-roman 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题

贪心解题，先取面额大的，转成罗马数字

class Solution {
public:
    string intToRoman(int num) {
        vector<pair<int, string>> v{
							        {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"}};
        string ans;
        for(int i = 0; i < v.size(); ++i)
        {
        	while(num-v[i].first >= 0)
        	{
        		ans += v[i].second;
        		num -= v[i].first;
        	}
        }
        return ans;
    }
};