[leetcode] 12/13 integer <=> roman

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

image.png

For example, two is written as II in Roman numeral, just two one's added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

• 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.
  Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999.

这题是 把 十进制整数 参照罗马数字和整数的对应关系 转化为 罗马数字。
并且 num 在 [1,3999] 之间.

由于 罗马数字 把每个数字位都规定了特定的符号，所以我们完全可以 个十百千 4个数字位分开处理。
所以 我们看到 下图黄色 的部分代表 每一位的1. ["I","X","C","M"]
那理论上我们每位重复1 就可以表示数字了，但罗马数字他不，
他 类似5进制， 有专门的符号表示5，就是下图 绿色部分 代表 每位上如果大于等于5 的情况下， 5要用["D","L","V"] 表示， 余下继续补1
本以为这样就完事了，罗马数字他不，他每位上出现4， 9 还要搞特殊。
所以我们遇到 4，9 就单独处理一下就好了。

image.png

总结一下就是

• 4，9 单独处理
• 大于等与5 --> 用5的符号
• 剩下都补1

 def help(self,n,_1,_4,_5,_9 ):
        n = int(n)
        ans =""
        if n == 4:
            return _4
        if n==9:
            return _9
        if n >= 5:
            ans+=_5
            n = n-5    
        ans = ans + _1*n
        return ans        

这里用 python 写了下

class Solution:
    def help(self,n,_1,_4,_5,_9 ):
        n = int(n)
        ans =""
        if n == 4:
            return _4
        if n==9:
            return _9
        if n >= 5:
            ans+=_5
            n = n-5    
        ans = ans + _1*n
        return ans        
    
    def intToRoman(self, num):
        """
        :type num: int
        :rtype: str
        """
        ans = ""
        num = str(num)
        if len(num) > 0:
            ans = self.help( num[-1],'I',"IV","V","IX" ) + ans
        if len(num) > 1:
            ans =self.help( num[-2],'X',"XL","L","XC" ) + ans
        if len(num) > 2:
            ans =self.help( num[-3],'C',"CD","D","CM" ) + ans
        if len(num)>3:
            ans = int(num[-4])*"M" + ans
        return ans

image.png

roman to integer

转回来就更简单了

因为 罗马字符天然有 一个性质 就是 从 right --> left， 是递增的,所以只要从右往左累加字符的值就好了。
如果发现右边得符号 值变小了， 那一定是 4，9 搞得事情。这个时候 减掉这个符号的值就好了。

这里用C 草写了一哈。。。。
吐槽一下 c 草 这个 iterator to string 转换的真6 。。。

#include <unordered_map>
#include <string>
using namespace std;
class Solution {
public:
    int romanToInt(string s) {
        
        unordered_map<string, int> up = {
            {"I", 1}, {"V", 5}, {"X", 10}, 
            {"C", 100}, {"L", 50}, {"D", 500}, {"M", 1000}};
        
        int sum = 0;
        string last="";
        
        for(auto it=s.rbegin();it!=s.rend();it++){
            
            // iterator --> string
            string i(1,*it);
            
            if( !last.empty() && up[i] < up[last]){
                sum-=up[i];
                continue;
            }
            
            sum+=up[i];
            last = i;

        }

        return sum;

    }
};

image.png