未分類

Integer to Roman

Go, LeetCode, Math, String

Integer to Roman

Given an integer, convert it to a roman numeral.

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

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

Default:

1
2
3
func intToRoman(num int) string {
}

解答思路:

建議可以先從之前寫過的Roman to Integer開始看並了解其中的規律，在了解規律的前提下再來解此題會快非常多，總之就是針對每一位數各別處理，再仔細觀查會發現每一位數轉成羅馬符號主要分成四塊，以1~9為例分別是IX(9),V(III)[8~5],IV(4),III(3~1)，只要能掌握這個規則，剩下就只是倍數與對應的符號關係。

程式碼解說:

因為要針對每一位數各別處理，將原數與10相除取餘數取得個位數字，接著與100相除取餘數取得十位數字等等，因此最一開始先初始化除數為10，當要向下取得下一位數字時才再將除數乘上10，接著是初始化羅馬符號中會出現的字母與其對應的數字，因為這次我們是要將數字轉為羅馬符號，因此在放入hashmap之中時，key值為數字，而value才是對應的羅馬符號

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

再來就是正式開始處理我們的數字，當數字歸0時表示處理完畢才回傳結果，否則就將該數與除數相除(初始化為10)分別取得個、十、百等位數的數字，並在取出之後將原數與取出的位數相減，接著才將各位數賦予對應的羅馬數字，稍後會分作四個部分來解說，拿到對應的羅馬數字才將除數乘上10以取得下一位數字

1
2
3
4
5
6
7
for num > 0 {
	tmp = num % div
	num -= tmp
	...
	div *= 10
}
return result

如果該位數開頭為9(9,90,900)，因為對應的羅馬符號表示是IX(10-1),XC(100-10),CM(1000-100)，正好是我們的(除數)與(除數再除10)，所以就將這兩個值放入hashmap之中找出對應的羅馬符號，注意符號是一個個放入結果值的開頭，所以要從後頭的符號開始放

1
2
3
4
if tmp == 9*(div/10) {
	result = roman[div] + result
	result = roman[div/10] + result
}

除去前述的情況，如果開頭為8~5(8~5,80~50,800~500)，以8為例對應的羅馬符號是VIII(5+1+1+1)，正好是我們的(除數再除2)與(除數再除10)x3，一樣從hashmap之中找出對應的羅馬符號，並且因為從後頭開始放起，所以先以迴圈算出後頭(除數再除10)要放多少個，最後才放(除數再除2)

1
2
3
4
5
6
else if tmp >= 5*(div/10) {
	for i := 1; i <= (tmp-5*(div/10))/(div/10); i++ {
		result = roman[div/10] + result
	}
	result = roman[div/2] + result
}

除去前述的情況，如果該位數開頭為4(4,40,400)，因為對應的羅馬符號表示是IV(5-1),XL(50-10),CD(500-100)，正好是我們的(除數再除2)與(除數再除10)，所以就將這兩個值放入hashmap之中找出對應的羅馬符號，注意符號是一個個放入結果值的開頭，所以要從後頭的符號開始放

1
2
3
4
else if tmp == 4*(div/10) {
	result = roman[div/2] + result
	result = roman[div/10] + result
}

除去前述的情況，如果開頭為3~1(3~1,30~10,300~100)，以3為例對應的羅馬符號是III(1+1+1)，正好是我們的(除數再除10)x3，一樣從hashmap之中找出對應的羅馬符號，以迴圈算出後頭(除數再除10)要放多少個再一一放入結果開頭

1
2
3
4
5
else {
	for i := 1; i <= tmp/(div/10); i++ {
		result = roman[div/10] + result
	}
}

完整程式碼:

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
29
30
31
32
33
34
35
func intToRoman(num int) string {
	var result string
	var tmp int
	div := 10
	roman := make(map[int]string)
	roman[1] = "I"
	roman[5] = "V"
	roman[10] = "X"
	roman[50] = "L"
	roman[100] = "C"
	roman[500] = "D"
	roman[1000] = "M"
	for num > 0 {
		tmp = num % div
		num -= tmp
		if tmp == 9*(div/10) {
			result = roman[div] + result
			result = roman[div/10] + result
		} else if tmp >= 5*(div/10) {
			for i := 1; i <= (tmp-5*(div/10))/(div/10); i++ {
				result = roman[div/10] + result
			}
			result = roman[div/2] + result
		} else if tmp == 4*(div/10) {
			result = roman[div/2] + result
			result = roman[div/10] + result
		} else {
			for i := 1; i <= tmp/(div/10); i++ {
				result = roman[div/10] + result
			}
		}
		div *= 10
	}
	return result
}

總結:

要將一數字轉為羅馬符號，主要就是針對每一位數各別處理，仔細觀查會發現每一位數轉成羅馬符號主要分成四塊，以1~9為例分別是IX(9),V(III)[8~5],IV(4),III(3~1)，只要能掌握這個規則，剩下就只是倍數與對應的符號關係。

分享到