C++實(shí)現(xiàn)LeetCode(13.羅馬數(shù)字轉(zhuǎn)化成整數(shù))
[LeetCode] 13. Roman to Integer 羅馬數(shù)字轉(zhuǎn)化成整數(shù)
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
For example, two is written as II in Roman numeral, just two one's added together. Twelve is written as, XII, which is simply X+ II. The number twenty seven is written as XXVII, which is XX + V + II.
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:
- I can be placed before V (5) and X(10) to make 4 and 9.
- X can be placed before L (50) and C (100) to make 40 and 90.
- C can be placed before D (500) and M (1000) to make 400 and 900.
Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.
Example 1:
Input: "III"
Output: 3
Example 2:
Input: "IV"
Output: 4
Example 3:
Input: "IX"
Output: 9
Example 4:
Input: "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.
Example 5:
Input: "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
羅馬數(shù)轉(zhuǎn)化成數(shù)字問題,我們需要對(duì)于羅馬數(shù)字很熟悉才能完成轉(zhuǎn)換。以下截自百度百科:
I - 1
V - 5
X - 10
L - 50
C - 100
D - 500
M - 1000
class Solution { public: int romanToInt(string s) { int res = 0; unordered_map<char, int> m{{'I', 1}, {'V', 5}, {'X', 10}, {'L', 50}, {'C', 100}, {'D', 500}, {'M', 1000}}; for (int i = 0; i < s.size(); ++i) { int val = m[s[i]]; if (i == s.size() - 1 || m[s[i+1]] <= m[s[i]]) res += val; else res -= val; } return res; } };
我們也可以每次跟前面的數(shù)字比較,如果小于等于前面的數(shù)字,先加上當(dāng)前的數(shù)字,比如 "VI",第二個(gè)字母 'I' 小于第一個(gè)字母 'V',所以要加1。如果大于的前面的數(shù)字,加上當(dāng)前的數(shù)字減去二倍前面的數(shù)字,這樣可以把在上一個(gè)循環(huán)多加數(shù)減掉,比如 "IX",我們?cè)?i=0 時(shí),加上了第一個(gè)字母 'I' 的值,此時(shí)結(jié)果 res 為1。當(dāng) i=1 時(shí),字母 'X' 大于前一個(gè)字母 'I',這說明前面的1是要減去的,而由于前一步不但沒減,還多加了個(gè)1,所以此時(shí)要減去2倍的1,就是減2,所以才能得到9,整個(gè)過程是 res = 1 + 10 - 2 = 9,參見代碼如下:
解法二:
class Solution { public: int romanToInt(string s) { int res = 0; unordered_map<char, int> m{{'I', 1}, {'V', 5}, {'X', 10}, {'L', 50}, {'C', 100}, {'D', 500}, {'M', 1000}}; for (int i = 0; i < s.size(); ++i) { if (i == 0 || m[s[i]] <= m[s[i - 1]]) res += m[s[i]]; else res += m[s[i]] - 2 * m[s[i - 1]]; } return res; } };
到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(13.羅馬數(shù)字轉(zhuǎn)化成整數(shù))的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)羅馬數(shù)字轉(zhuǎn)化成整數(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
- C++實(shí)現(xiàn)LeetCode(88.混合插入有序數(shù)組)
- C++實(shí)現(xiàn)LeetCode(21.混合插入有序鏈表)
- C++實(shí)現(xiàn)LeetCode(20.驗(yàn)證括號(hào))
- C++實(shí)現(xiàn)LeetCode(19.移除鏈表倒數(shù)第N個(gè)節(jié)點(diǎn))
- C++實(shí)現(xiàn)LeetCode(18.四數(shù)之和)
- C++實(shí)現(xiàn)LeetCode(14.最長共同前綴)
- C++實(shí)現(xiàn)LeetCode(24.成對(duì)交換節(jié)點(diǎn))
相關(guān)文章
C語言實(shí)現(xiàn)求解素?cái)?shù)的N種方法總結(jié)
哈嘍各位友友們,今天又學(xué)到了很多有趣的知識(shí),現(xiàn)在迫不及待的想和大家分享一下!本文將手把手帶領(lǐng)大家探討利用試除法、篩選法求解素?cái)?shù)的n層境界!都是精華內(nèi)容,可不要錯(cuò)過喲2023-01-01基于C語言實(shí)現(xiàn)圖書管理信息系統(tǒng)設(shè)計(jì)
這篇文章主要為大家詳細(xì)介紹了基于C語言實(shí)現(xiàn)圖書管理信息系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2018-01-01關(guān)于C++虛函數(shù)與靜態(tài)、動(dòng)態(tài)綁定的問題
這篇文章主要介紹了C++虛函數(shù)與靜態(tài)、動(dòng)態(tài)綁定,本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2021-10-10c++中移動(dòng)語義和完美轉(zhuǎn)發(fā)及易錯(cuò)點(diǎn)
C++ 中的移動(dòng)語義和完美轉(zhuǎn)發(fā)是 C++11 引入的兩個(gè)重要特性,它們分別用于提高性能和靈活性,這篇文章主要介紹了c++中移動(dòng)語義和完美轉(zhuǎn)發(fā),需要的朋友可以參考下2023-09-09