leetcode-13-Roman-to-Integer

发表于   |  

描述

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

分析

罗马数字转化为阿拉伯数字，中文wiki上有转换规则，简单来说就是，每一个罗马数字代表一个数值，从左至右，如果右边的数值比左边的小，那么依次加上，如果右边的数值比左边的大，那么就需要减去这个值，比如罗马数字 XIV，转化为阿拉伯数字就是10-1+5，实际上可以写成 10+1+(5-1*2)，也就是，只要右边小于左边，依次加上，但右边大于左边，减去两倍之前加上的左边的值。

解决方案1(C)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int romanToInt(char* s) {
    int table[256];
    table['I'] = 1;
    table['V'] = 5;
    table['X'] = 10;
    table['L'] = 50;
    table['C'] = 100;
    table['D'] = 500;
    table['M'] = 1000;
    int res = table[s[0]];
    for(int i = 1; i < strlen(s); i++){
        if(table[s[i]] <= table[s[i-1]]){
            res += table[s[i]];
        }else {
            res += table[s[i]] - 2*table[s[i-1]];
        }
    }
    return res;
}

当然如果从右边往左边看也可以，如 XIV 就等于5-1+10

解决方案2(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {  
public:  
    int romanToInt(string s) {   
        int table[256];
        
        table['I'] = 1;
        table['V'] = 5;
        table['X'] = 10;
        table['L'] = 50;
        table['C'] = 100;
        table['D'] = 500;
        table['M'] = 1000;
        int result = table[s[s.length()-1]];
        for(int i = s.length()-2; i >= 0; i--){\
            if(table[s[i]] >= table[s[i+1]]){
                result += table[s[i]];
            }else {
                result -= table[s[i]];
            }
        }
        return result;
    }
};

解决方案3(Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        roman2int = {"I":1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
        result = 0
        for index, value in enumerate(s):
            if index>0 and roman2int[value]>roman2int[s[index-1]]:
                result += (roman2int[value]-2*roman2int[s[index-1]])
            else:
                result += roman2int[value]
        return result

解决方案4(Rust)

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
use std::collections::HashMap;

impl Solution {
    pub fn roman_to_int(s: String) -> i32 {
        let table: HashMap<char, i32> = [
            ('M', 1000),
            ('D', 500),
            ('C', 100),
            ('L', 50),
            ('X', 10),
            ('V', 5),
            ('I', 1)
        ].iter().cloned().collect();
        
        let mut result = 0;
        let mut pre = 'I';
        
        for current in s.chars().rev() {
            if table.get(&current).unwrap() < table.get(&pre).unwrap() {
                result -= table.get(&current).unwrap();
            } else {
                result += table.get(&current).unwrap();
            }
            pre = current;
        }
        result
    }
}

相关问题

题目来源