未分類

Integer to Roman

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),只要能掌握這個規則,剩下就只是倍數與對應的符號關係。

分享到