letcode[013] 罗马数字转整数

题目013

题目地址：罗马数字转整数

1. 主要涉及到对字符串的分割，分割间断的选择问题。
2. 方法3体现了对题意理解的角度问题，感觉是神仙方法。

思路1：自拟思路——建立字符串和数字映射表，先处理特殊情况

建立罗马字符和数字的对应关系字典，针对特殊情况，首先判断出特殊情况的字符，并从字符串中移出，剩下非特殊字符，然后对特殊字符和非特殊字符对照字典加和即可
总结：感谢罗马数字80的写法是LXXX，而不是XLXL
用时：172 ms

s="MCMXCIV"
def romanToInt1(s):
    rm_letter=["I","V","X","L","C","D","M","IV","IX","XL","XC","CD","CM"]
    rm_num=[1,5,10,50,100,500,1000,4,9,40,90,400,900]
    letter_dict={rm_letter[i]:rm_num[i] for i in range(len(rm_num))}
    sub_rm_letter=["IV","IX","XL","XC","CD","CM"]
    #遍历获取字符串中是否含有子数据，并进行替换
    all_letter=[]
    for sb_lt in sub_rm_letter:
        if sb_lt in s:
            all_letter.append(sb_lt)
            s=s.replace(sb_lt,"")
    #将余下的数据添加到罗马字符列表中
    all_letter.extend(list(s))
    num=0
    for letter in all_letter:
        num+=letter_dict[letter]
    return num

思路2：网友思路——建立字符串和数据映射表，依次处理

建立罗马字符和数字的对应关系字典，对罗马字符串从左到右开始匹配，先匹配2个字符串的罗马字符，匹配到了则将下一次匹配开始位置增加2，如果没有匹配到则下一次匹配其实位置增加1。
总结：这思路比用判断谁在谁之前的好哇
用时：124 ms

def romanToInt2(s):
    dict1={'M':1000,'CM':900,'D':500,'CD':400,'C':100,'XC':90,'L':50,'CL':40,'X':10,'IX':9,'V':5,'IV':4,'I':1}
    i=0
    result=0
    while 1:
        if i<=(len(s)-1):
            try:
                if dict1[s[i:(i+2)]]:
                    result +=dict1[s[i:(i+2)]]
                    i=i+2
            except:
                result +=dict1[s[i]]
                i=i+1
        else:
            break
    return result

思路3：网友思路——奇巧淫技

这个要费点脑子，可以说是奇巧淫技了。罗马数字共13种情形，其中6中，是变体。其实把这6种特殊情况倒过来看，就是一个大数减去了它后面符号代表的小数，如IV：就是V-I。也就是说，将罗马数字的顺序反转过来，然后从第一位开始将各个字符的数字相加，如果某位的数字是小于前一位的，则将该位的符号变为减。
总结： 这里利用了罗马数字的特性：从左到右，数字排列是从大到小的。数字系列反过来时，如果后一位比前一位小，则说明是有减除的。
用时： 124 ms

def romanToInt3(s):
    roman = {'M': 1000,'D': 500 ,'C': 100,'L': 50,'X': 10,'V': 5,'I': 1}
    carry = 0
    res = 0
    for letter in s[::-1]:
        cur = roman[letter]
        if cur >= carry:
            res += cur
        else:
            res -= cur
        carry = max(cur, carry)
    return res