LeetCode #13 Roman to Integer - 刷題之旅
1 題目描述
和上一題相反,將羅馬數字轉換成阿拉伯數字。
2 解法
2.1 我的作法
我一開始想的比較複雜,是想要使用while迴圈,從第一個字串與第二個字串開始比較,一般來說羅馬字是由大排到小,因此一但發現“前面” < "後面“ (由小到大),前面要當減數,否則就是加法。
大概是這種感覺:
1 | class Solution(object): |
時間複雜度:O(n)
- n 是輸入字浮串的長度,這個解法只需要一次迭代。
空間複雜度:O(1)
- 固定空間:儲存字典 num_dic,這是固定的大小,包含 7 個元素。
- 變量:變量 left、right 和 sum 使用固定的額外空間。
- 函數沒有使用額外的空間來儲存與輸入大小相關的數據結構,因此空間複雜度為 O(1)
2.2 更簡潔
但是有更簡潔的寫法,概念一樣,但是不用while迴圈,直接用for迴圈就可以了。
1 | def romanToInt(self, s): |
3 結論
這題感覺難度也不會很難,是可以自己想出來的。
本部落格所有文章除特別聲明外,均採用 CC BY-NC-SA 4.0 許可協議。轉載請註明來自 Shannon's Blog 🐟 技術 | 生活 | 旅行! 如果你覺得我的文章有幫助,希望你可以到我的 github 給我一個 star ⭐️ Shannon Blog Repo
評論