每周算法:罗马数字转阿拉伯数字

Description

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.

来源:leetcode 13 roman to integer

Solution

Approach 1

这道题不是很难,很容易就能想到解法,需要注意好边界条件问题,下面就是我的解法。

pint romanToInt(string str) {
    int ans = 0;
    int pos = 0;
    const int len = str.length();

    // 千位
    while (pos < len && str[pos] == 'M') {
	++pos;
    }
    ans += 1000 * pos;
    if (pos == len) {
	return ans;
    }

    // 百位
    switch (str[pos]) {
    case 'C':
	ans += 100;
	++pos;

	if (str[pos] == 'D') {
	    ans += 300;
	    ++pos;
	}
	else if (str[pos] == 'M') {
	    ans += 800;
	    ++pos;
	}
	else {
	    while (pos < len && str[pos] == 'C') {
		ans += 100;
		++pos;
	    }
	}
	break;

    case 'D':
	ans += 500;
	++pos;
	while (pos < len && str[pos] == 'C') {
	    ans += 100;
	    ++pos;
	}
	break;

    default:
	break;
    }
    if (pos == len) {
	return ans;
    }

    // 十位
    switch (str[pos]) {
    case 'X':
	ans += 10;
	++pos;

	if (str[pos] == 'C') {
	    ans += 80;
	    ++pos;
	}
	else if (str[pos] == 'L'){
	    ans += 30;
	    ++pos;
	}
	else {
	    while (pos < len && str[pos] == 'X') {
		ans += 10;
		++pos;
	    }
	}
	break;

    case 'L':
	ans += 50;
	++pos;
	while (pos < len && str[pos] == 'X') {
	    ans += 10;
	    ++pos;
	}
	break;

    default:
	break;
    }
    if (pos == len) {
	return ans;
    }

    // 个位
    switch (str[pos]) {
    case 'I':
	ans += 1;
	++pos;
	if (str[pos] == 'X') {
	    ans += 8;
	    ++pos;
	}
	else if (str[pos] == 'V') {
	    ans += 3;
	    ++pos;
	}
	else {
	    while (pos < len && str[pos] == 'I') {
		++ans;
		++pos;
	    }
	}

	break;
    case 'V':
	ans += 5;
	++pos;
	while (pos < len && str[pos] == 'I') {
	    ++ans;
	    ++pos;
	}
	break;
    default:
	break;
    }

    return ans;
}

不得不说,这样的代码比较丑,这是真的,就算解出来了成就感也不强。

Approach 2

这个解法是leetcode上最快的解法之一,只使用一个循环就完成了计算,代码整体上很简洁,也比较好理解。只需要针对6种特殊情况做特殊处理就好。

int romanToInt(string s) {
    int result = 0;
    int size = s.size();
    for(int i = 0; i < size; ++i) {
	switch(s[i]) {
	case 'M':
	    if(i - 1 >= 0 && s[i - 1] == 'C')
		result += 800;
	    else
		result += 1000;
	    break;

	case 'D':
	    if(i - 1 >= 0 && s[i - 1] == 'C')
		result += 300;
	    else
		result += 500;
	    break;

	case 'C':
	    if(i - 1 >= 0 && s[i - 1] == 'X')
		result += 80;
	    else
		result += 100;
	    break;

	case 'L':
	    if(i - 1 >= 0 && s[i - 1] == 'X')
		result += 30;
	    else
		result += 50;
	    break;

	case 'X':
	    if(i - 1 >= 0 && s[i - 1] == 'I')
		result += 8;
	    else
		result += 10;
	    break;

	case 'V':
	    if(i - 1 >= 0 && s[i - 1] == 'I')
		result += 3;
	    else
		result += 5;
	    break;

	case 'I':
	    result += 1;
	    break;

	default:;
	}
    }
    return result;
}

Approach 3

下面这个是我在看该问题的discuss板块的时候发现的。不得不说,结题思路实在新奇,这点是值得学习的。不过我比较担心它的时间复杂度。该方法使用Java编写。

public int romanToInt(String s) {
    int sum=0;
    if(s.indexOf("IV")!=-1){sum-=2;}
    if(s.indexOf("IX")!=-1){sum-=2;}
    if(s.indexOf("XL")!=-1){sum-=20;}
    if(s.indexOf("XC")!=-1){sum-=20;}
    if(s.indexOf("CD")!=-1){sum-=200;}
    if(s.indexOf("CM")!=-1){sum-=200;}

    char c[]=s.toCharArray();
    int count=0;

    for(;count<=s.length()-1;count++){
	if(c[count]=='M') sum+=1000;
	if(c[count]=='D') sum+=500;
	if(c[count]=='C') sum+=100;
	if(c[count]=='L') sum+=50;
	if(c[count]=='X') sum+=10;
	if(c[count]=='V') sum+=5;
	if(c[count]=='I') sum+=1;
    }

    return sum;
}

Comments

Comments powered by Disqus