Skip to content

Latest commit

 

History

History
160 lines (125 loc) · 4.46 KB

0013._Roman_to_Integer.md

File metadata and controls

160 lines (125 loc) · 4.46 KB

13.Roman to Integer

难度: Easy

刷题内容

原题连接

内容描述

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

Symbol       Value
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.

Example 1:

Input: "III"
Output: 3
Example 2:

Input: "IV"
Output: 4
Example 3:

Input: "IX"
Output: 9
Example 4:

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

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

解题方案

思路 1

罗马数字是最古老的数字表示方式，比阿拉伯数组早2000多年，起源于罗马

罗马数字有如下符号：

基本字符	        I       V	X	L	C       D       M
对应阿拉伯数字	1	5	10	50	100	500	1000

计数规则：
- 相同的数字连写，所表示的数等于这些数字相加得到的数，例如：III = 3
- 小的数字在大的数字右边，所表示的数等于这些数字相加得到的数，例如：VIII = 8
- 小的数字，限于（I、X和C）在大的数字左边，所表示的数等于大数减去小数所得的数，例如：IV = 4,这条规则好像这题不管
- 正常使用时，连续的数字重复不得超过三次
- 在一个数的上面画横线，表示这个数扩大1000倍（本题只考虑3999以内的数，所以用不到这条规则）
- 从前向后遍历罗马数字，如果某个数比前一个数小，则加上该数。反之，减去前一个数的两倍然后加上该数

integer to Roman 是 Medium，这个roman to integer是easy

  • 从前往后扫描，用一个临时变量记录分段数字。
  • 如果当前比前一个大，说明这一段的值应当是这个值减去上一个值。比如IV = 5-1 =4; 否则，将当前值加入到结果中，然后开始下一段记录，比如VI = 5 + 1, II = 1 +1

AC代码

class Solution(object):
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        lookup = {
            'I': 1,
            'V': 5,
            'X': 10,
            'L': 50,
            'C': 100,
            'D': 500,
            'M': 1000
        }
        res = 0
        for i in range(len(s)):
            if i > 0 and lookup[s[i]] > lookup[s[i-1]]:
                res += lookup[s[i]] - 2 * lookup[s[i-1]]
            else:
                res += lookup[s[i]]
        return res

或者甚至可以建立一个新函数用于取对应数值：

        def table(x):
            return {
                   'I':1,
                   'V':5,
                   'X':10,
                   'L':50,
                   'C':100,
                   'D':500,
                   'M':1000
                }.get(x)

思路 2

除了 6 种特殊情况是双字母，其他都是单字母，并且任意一个数，特定特殊情况只会出现一次，因此先汇总特殊情况，再遍历叠加单字母即可

class Solution:
    def romanToInt(self, s: str) -> int:
        d = {
            'IV': 4,
            'IX': 9,
            'XL': 40,
            'XC': 90,
            'CD': 400,
            'CM': 900,
            'I': 1,
            'V': 5,
            'X': 10,
            'L': 50,
            'C': 100,
            'D': 500,
            'M': 1000
        }
        total = 0
        for v in ['IV', 'IX', 'XL', 'XC', 'CD', 'CM']:
            if v in s:
                total += d[v]
                s = s.replace(v, '')
        for v in s:
            total += d[v]
        return total