未分類

Roman to Integer

Go, LeetCode, Math, String

Roman to Integer

Given a roman numeral, convert it to an integer.

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

提示 解題應用
Math 規律觀察
String 規律觀察

Default:

1
2
func romanToInt(s string) int {
}

解答思路:

對於沒碰過羅馬數字的人來說，可能要先去查查羅馬數字的規則才有辦法將問題給寫出來，所以第一件要做的事便事去搜尋羅馬數字並觀查其規律，不過所幸給予的數字並非無限大，所以只需觀查1~3999的範圍即可，而我們可以得知:

個位數字母規律

1: I

2: II

3: III

而到5的倍數前一個數字便是以 (5n - 1) 的方式做表達(要相減的數字放置於前面)

4: IV (5n - 1)

5: V

5的倍數之後到下一個倍數之前便是以 (5n + 1) 的方式做表達(要相加的數字放置於後面)

6: VI

7: VII

8: VIII

9: IX (5n - 1)

10: X

10的倍數字母規律

10: X

20: XX

30: XXX

而到10的倍數前一個數字便是以 (10n - 10) 的方式做表達(要相減的數字放置於前面)

40: XL

50: L

10的倍數之後到下一個倍數之前便是以 (10n + 10) 的方式做表達(要相加的數字放置於後面)

60: LX

70: LXX

80: LXXX

90: XC (10n - 10)

100: C

以此類推 最後只要曉得500與1000的字母便已經有寫出羅馬數字1~9999的能力了

500: D

1000: M

整理一下全部羅馬字母大小順序的話會得到:

M → D → C → L → X → V → I

到這邊我想到的作法便是將問題所給予的羅馬數字從頭開始分拆來看，我們可以發現到與千位數有關的就是M，因為數字不會到5000，所以基本上不用擔心千位數的變化，百位數有關的就是D與C了，如果在讀百位數的羅馬數字DC時若是先C再往下卻又是比較大的D時，此時就要相減 CD: (500-100) ，繼續往下走碰到十位數的LX時，就可以曉得百位數字合就到此為止了，而如果是X再往下卻又是百位數字的C，便可以曉得此時為 XC: (100-10) 以此類推。

此時再稍思考一下便可知道: 如果下一個字母小於當前字母就與總合相加，否則就要與總合相減。

程式碼解說:

首先我們至少需要先把每個羅馬符號對應哪個數字記錄下來，你可以用常數定義好再用switch去取出值，或是像有些語言有enum(列舉)再去用switch取出，而這邊我就直接用map來存取比較方便。

1
2
3
4
5
6
7
8
roman := make(map[string]int)
roman["I"] = 1
roman["V"] = 5
roman["X"] = 10
roman["L"] = 50
roman["C"] = 100
roman["D"] = 500
roman["M"] = 1000

關鍵就在於這段，只是將上述得到的結論實作出來，如果下一個字母小於當前字母就與總合相加，否則就要與總合相減，這邊要注意一下當到最後一個羅馬符號的時候就沒辦法在拿下一個符號了，這時就直接將結果與總合相加即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
for key, value := range s {
	r = roman[string(value)]
	if key+1 < slen {
		nr = roman[string(s[key+1])]
		if r >= nr {
			sum += r
		} else {
			sum -= r
		}
	} else {
		sum += r
	}
}

完整程式碼:

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
func romanToInt(s string) int {
	roman := make(map[string]int)
	roman["I"] = 1
	roman["V"] = 5
	roman["X"] = 10
	roman["L"] = 50
	roman["C"] = 100
	roman["D"] = 500
	roman["M"] = 1000
	sum := 0
	slen := len(s)
	var r int
	var nr int
	for key, value := range s {
		r = roman[string(value)]
		if key+1 < slen {
			nr = roman[string(s[key+1])]
			if r >= nr {
				sum += r
			} else {
				sum -= r
			}
		} else {
			sum += r
		}
	}
	return sum
}

總結:

羅馬符號轉數字: 從字串開頭一一取出字元，如果當前字母大於下一個字母就與總合相加，否則與總合相減。

分享到