欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++實(shí)現(xiàn)LeetCode(13.羅馬數(shù)字轉(zhuǎn)化成整數(shù))

 更新時(shí)間:2021年07月12日 17:03:09   作者:Grandyang  
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(13.羅馬數(shù)字轉(zhuǎn)化成整數(shù)),本篇文章通過簡要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下

[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)換。以下截自百度百科:

羅馬數(shù)字是最早的數(shù)字表示方式,比阿拉伯?dāng)?shù)字早2000多年,起源于羅馬。
如今我們最常見的羅馬數(shù)字就是鐘表的表盤符號(hào):Ⅰ,Ⅱ,Ⅲ,Ⅳ(IIII),Ⅴ,Ⅵ,Ⅶ,Ⅷ,Ⅸ,Ⅹ,Ⅺ,Ⅻ……
對(duì)應(yīng)阿拉伯?dāng)?shù)字(就是現(xiàn)在國際通用的數(shù)字),就是1,2,3,4,5,6,7,8,9,10,11,12。(注:阿拉伯?dāng)?shù)字其實(shí)是古代印度人發(fā)明的,后來由阿拉伯人傳入歐洲,被歐洲人誤稱為阿拉伯?dāng)?shù)字。)

I - 1

V - 5

X - 10

L - 50

C - 100 

D - 500

M - 1000

1、相同的數(shù)字連寫,所表示的數(shù)等于這些數(shù)字相加得到的數(shù),如:Ⅲ = 3;
2、小的數(shù)字在大的數(shù)字的右邊,所表示的數(shù)等于這些數(shù)字相加得到的數(shù), 如:Ⅷ = 8;Ⅻ = 12;
3、小的數(shù)字,(限于Ⅰ、X 和C)在大的數(shù)字的左邊,所表示的數(shù)等于大數(shù)減小數(shù)得到的數(shù),如:Ⅳ= 4;Ⅸ= 9;
4、正常使用時(shí),連寫的數(shù)字重復(fù)不得超過三次。(表盤上的四點(diǎn)鐘“IIII”例外)
5、在一個(gè)數(shù)的上面畫一條橫線,表示這個(gè)數(shù)擴(kuò)大1000倍。
有幾條須注意掌握:
1、基本數(shù)字Ⅰ、X 、C 中的任何一個(gè),自身連用構(gòu)成數(shù)目,或者放在大數(shù)的右邊連用構(gòu)成數(shù)目,都不能超過三個(gè);放在大數(shù)的左邊只能用一個(gè)。
2、不能把基本數(shù)字V 、L 、D 中的任何一個(gè)作為小數(shù)放在大數(shù)的左邊采用相減的方法構(gòu)成數(shù)目;放在大數(shù)的右邊采用相加的方式構(gòu)成數(shù)目,只能使用一個(gè)。
3、V 和X 左邊的小數(shù)字只能用Ⅰ。
4、L 和C 左邊的小數(shù)字只能用X。
5、D 和M 左邊的小數(shù)字只能用C。
而這道題好就好在沒有讓我們來驗(yàn)證輸入字符串是不是羅馬數(shù)字,這樣省掉不少功夫。需要用到 HashMap 數(shù)據(jù)結(jié)構(gòu),來將羅馬數(shù)字的字母轉(zhuǎn)化為對(duì)應(yīng)的整數(shù)值,因?yàn)檩斎氲囊欢ㄊ橇_馬數(shù)字,那么只要考慮兩種情況即可:
第一,如果當(dāng)前數(shù)字是最后一個(gè)數(shù)字,或者之后的數(shù)字比它小的話,則加上當(dāng)前數(shù)字。
第二,其他情況則減去這個(gè)數(shù)字。
解法一:
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)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • C語言實(shí)現(xiàn)求解素?cái)?shù)的N種方法總結(jié)

    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ì)

    基于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)綁定的問題

    關(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-10
  • C語言指針超詳細(xì)講解上篇

    C語言指針超詳細(xì)講解上篇

    指針提供了對(duì)地址操作的一種方法,因此,使用指針可使得?C?語言能夠更高效地實(shí)現(xiàn)對(duì)計(jì)算機(jī)底層硬件的操作。另外,通過指針可以更便捷地操作數(shù)組。在一定意義上可以說,指針是?C?語言的精髓
    2022-04-04
  • C語言中qsort函數(shù)的介紹與用法實(shí)例

    C語言中qsort函數(shù)的介紹與用法實(shí)例

    C語言的標(biāo)準(zhǔn)庫提供了一個(gè)重要的排序函數(shù)qsort給C語言使用者使用,qsort函數(shù)將快速排序的算法封裝起來,這篇文章主要給大家介紹了關(guān)于C語言中qsort函數(shù)的介紹與用法的相關(guān)資料,需要的朋友可以參考下
    2021-09-09
  • C語言掃雷游戲的實(shí)現(xiàn)方法

    C語言掃雷游戲的實(shí)現(xiàn)方法

    這篇文章主要為大家詳細(xì)介紹了C語言掃雷游戲的實(shí)現(xiàn)方法,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2021-06-06
  • c++中移動(dòng)語義和完美轉(zhuǎn)發(fā)及易錯(cuò)點(diǎn)

    c++中移動(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
  • 詳解C語言fscanf函數(shù)讀取文件教程及源碼

    詳解C語言fscanf函數(shù)讀取文件教程及源碼

    這篇文章主要為大家介紹了詳解C語言算法fscanf讀取文件示例教程,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步
    2022-02-02
  • C++ Vector迭代器失效問題的解決方法

    C++ Vector迭代器失效問題的解決方法

    最近我學(xué)習(xí)了C++中的迭代器失效問題,迭代器失效問題是非常非常重要的,所以特意整理出來一篇文章供我們一起復(fù)習(xí)和學(xué)習(xí)
    2022-08-08
  • 深入淺析STL vector用法

    深入淺析STL vector用法

    這篇文章給大家介紹 stl vector用法,主要知識(shí)點(diǎn)在如何恰當(dāng)?shù)氖褂盟鼈兊某蓡T函數(shù),涉及到條件函數(shù)和函數(shù)指針在迭代算法中的使用,對(duì)stl vector用法感興趣的朋友可以參考下本文
    2015-10-10

最新評(píng)論