罗马数字转数字

https://leetcode.com/problems/roman-to-integer/

Description

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

  • I: 1
  • V: 5
  • X: 10
  • L: 50
  • C: 100
  • D: 500
  • M: 1000

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

8个罗马数字 I, V, X, L, C, D, M 一个比一个大, 定义了从 1 到 1000, 用来描述其他数字, 但是逢4和9就会特殊处理, 4 是 5 - 1, 9 是 10 - 1, 问题是输入一个罗马数字字符串, 输出对应10进制数字

Example

Example 1:

1
2
Input: "III"
Output: 3

Example 2:

1
2
Input: "IV"
Output: 4

Example 3:

1
2
Input: "IX"
Output: 9

Example 4:

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

Example 5:

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

Answer

思路一

最开始判断的方法比较简单但是效率很低, 先把所有正常的和特殊的罗马字符定义在两个字典中, 取出来后死循环在字符串中判断, 看有没有, 有的话在结果上加对应的值, 然后再将其替换为空, 再在字符串中找, 直到将一个特殊字符在罗马字符串内替换没, break, 再机继续判断下一个特殊字符, 最后将所有的特殊字符都判断完了, 再判断正常的, 取值累加即可

思路二

尝试了几个罗马数字后发现规律, MCM = 1900 但是不按特殊字符相加就是 2100, 相差了两个 C, 同样的其他的特殊字符例如 MXC = 1090, 不按特殊字符相加的话是 1110, 相差了两个 X, 并且所有的特殊字符串都是两个字符, 并且第一个字符比第二个小, 所以不难发现其中规律, 有了这个规律后就可以更简单的解决这个问题了, 循环遍历字符串, 先按照正常值相加, 然后判断当前位与下一位字符是否满足特殊字符串的规律, 满足的话再减去 两倍的当前字符对应的值即可.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def roman_num_str_to_int(roman_num_str):
    """
    :type roman_num_str: str
    :rtype: int
    """
    normal = {
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000,
    }
    
    result = 0
    len_s = len(s)

    for index in xrange(len_s):
        current_roman = s[index]
        result += normal[current_roman]

        if index < len_s-1:
            next_roman = s[index+1]
            if normal[current_roman] < normal[next_roman]:
                result -= normal[current_roman] * 2

    return result