小屋創作

巴哈姆特 APP

專屬 ACG 勇者的廣闊世界

以 APP 瀏覽

日誌2020-07-26 00:00

LeetCode - 13. Roman to Integer 解題心得

作者:Not In My Back Yard

題目連結:
13. Roman to Integer


題目意譯:
羅馬數字有七個相異符號:I 、 V 、 X 、 L 、 C 、 D 以及 M 。
符號      值
I        1
V        5
X        10
L        50
C        100
D        500
M        1000

例如: 2 在羅馬數字表示法中被寫為 II ,就是兩個 1 並排在一起形成 2 ; 12 被寫作 XII ,即 X + II;數字 27 寫為 XXVII,則是 XX + V + II 。

羅馬數字基本上由大到小、從左至右書寫。但是,數字 4 的表示法並非為 IIII ,而是 IV 。因為寫在 V 前面的 I 代表我們應該要減去那個 I 值而形成了 4 。同樣地, 9 被寫為 IX 而非 XIIII。有六種情況會使用到這種減法規則:
I 可以放在 V (5) 和 X (10) 前面,形成 4 和 9.
X 可以放在 L (50) 和 C (100) 前面,形成 40 和 90.
C 可以放在 D (500) 和 M (1000) 前面,形成 400 和 900.

給定一個羅馬數字 s ,請將其轉為一個一般整數。輸入的值保證落在 1 ~ 3999 之間。



範例測資:
範例 1:
輸入: "III"
輸出: 3

範例 2:
輸入: "IV"
輸出: 4

範例 3:
輸入: "IX"
輸出: 9

範例 4:
輸入: "LVIII"
輸出: 58
解釋: L = 50 、 V = 5 、 III = 3.

範例 5:
輸入: "MCMXCIV"
輸出: 1994
解釋: M = 1000 、 CM = 900 、 XC = 90 且 IV = 4.


解題思維:
因為在沒有使用到減法規則時,羅馬數字是由大到小書寫的。因此掃過給定的數字 s 時,可以看看當前位數 s[i] 是否小於(以符號代表的值去看)下一位數 s[i + 1]。如果較小就表示該使用減法規則,即 s[i + 1] 符號代表的值 - s[i] 符號代表的值,並且迴圈下一個看的位置應為 i + 2 ,因為 s[i + 1] 已經使用過了。

如果 s[i] 沒有比較小,或是該位數已經是尾端了,沒有下一位數,則直接加上 s[i] 代表的值即可。



本人的程式碼(儲存於 CodePad)

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

0

0

LINE 分享

相關創作

ZeroJudge - b674: Is It A Tree 解題心得

ZeroJudge - c131: 00615 - Is It A Tree? 解題心得

LeetCode - 258. Add Digits 解題心得

留言

face基於日前微軟官方表示 Internet Explorer 不再支援新的網路標準,可能無法使用新的應用程式來呈現網站內容,在瀏覽器支援度及網站安全性的雙重考量下,為了讓巴友們有更好的使用體驗,巴哈姆特即將於 2019年9月2日 停止支援 Internet Explorer 瀏覽器的頁面呈現和功能。
屆時建議您使用下述瀏覽器來瀏覽巴哈姆特:
。Google Chrome(推薦)
。Mozilla Firefox
。Microsoft Edge(Windows10以上的作業系統版本才可使用)

face我們了解您不想看到廣告的心情⋯ 若您願意支持巴哈姆特永續經營,請將 gamer.com.tw 加入廣告阻擋工具的白名單中,謝謝 !【教學】