013. 羅馬數字轉整數 | Leetcode題解

2021-02-21 前端布道師
題目描述:

羅馬數字包含以下七種字符: I ， V ， X ， L ， C ， D 和 M 。

字符          數值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000
例如， 羅馬數字 2 寫做 II ，即為兩個並列的 1。12 寫做 XII ，即為 X + II 。 27 寫做 XXVII , 即為 XX + V + II 。
通常情況下，羅馬數字中小的數字在大的數字的右邊。但也存在特例，例如 4 不寫做 IIII ，而是 IV 。數字 1 在數字 5 的左邊，所表示的數等於大數 5 減小數 1 得到的數值 4 。同樣地，數字 9 表示為 IX 。這個特殊的規則只適用於以下六種情況：
I 可以放在 V (5) 和 X (10) 的左邊，來表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左邊，來表示 40 和90。
C 可以放在 D (500) 和 M (1000) 的左邊，來表示400 和900。
給定一個羅馬數字，將其轉換成整數。輸入確保在 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.
難度：支持語言：JavaScript、Python、C++相關標籤相關企業複雜度分析時間複雜度：由於左右指針移動的次數加起來正好是 n， 因此時間複雜度為 
Js中文網 - 前端進階資源教程 www.javascriptC.com,typescript 中文文檔Javascript中文網是以前端進階資源教程分享為主的專業網站，包括：前端、大廠面試題、typescript教程、程序人生、React.js……等，以幫助開發者成長為願景的社區
思路1：注意4和9是前一個數字比後一個數字小，其他都是前一個數字比後一個數字大。思路2：
羅馬數字轉換為阿拉伯數字的時候，實際上是從左到右將每個字符對應的值累加的過程。例如「XVI」，實際就是10（X）+5（V）+1（I）。
只不過由於存在特殊規則增加了這個過程的複雜，不過同樣可以用上面的思路解決。舉個例子，「IX」，可以看作是-1+10=9；「XIX」可以看作是10-1+10=19。
題目又告訴我們，通常情況下，羅馬數字中小的數字在大的數字的右邊。所以，如果s[i]<s[i+1]，那s[i]在累加時需要加一個負號，這就完成了特殊規則的處理。
思路3：利用switch語句將字符轉換成對應的數字，然後去判斷下一位字符是否比當前的字符大，若大則當前字符取相反數，然後sum++；思路4：
給定一個羅馬數字，將其轉為整數，輸入的數字在1到3999範圍內。已知：羅馬數字包含以下七種字符：I,V,X,L,C,D,M
轉換表為：
 字符     數值     進位
  I       1       個位值為1
  V       5       個位值為5
  X       10      十位值為1
  L       50      十位值為5
  C       100     百位值為1
  D       500     百位值為5
  M       1000    千位值為1
由羅馬數字表示規則可知
例如：4:IV    9:IX
    40:XL   90:XC
   400:CD  900:CM
可知：數值大小 == 大的數字位-小的數字位 ---- 《2》
可知：數值大小 == 大的數字位+小的數字位 ---- 《1》一般情況下 數字組成：大的數字位+小的數字位 ---- <1>但當羅馬數字進位值（個、十、百、千）== 9 或 == 4 時，數字組成變為：小的數字+大的數字 ---- <2>《1》 即 左邊的羅馬數字 > 右邊的羅馬數字時 => 羅馬數 == 左邊羅馬數字對應的阿拉伯數字 + 右邊羅馬數字對應的阿拉伯數字《2》 即 左邊的羅馬數字 < 右邊的羅馬數字時 => 羅馬數 == 左邊羅馬數字對應的阿拉伯數字的反數即負數 + 右邊羅馬數字對應的阿拉伯數字且 羅馬數字的轉換表在上意味著 所有數字都可以有其中的羅馬數字字符組成 => 建立羅馬數字和阿拉伯數字 Hash對照表遍歷羅馬數字 因為轉換表裡對應的阿拉伯數字帶有千、百、十和個位 所以 不需考慮9，99，999臨界位 直接求出總和即可代碼JavaScripe 實現
/**
 * @來源： Javascript中文網 - 前端進階資源教程 https://www.javascriptc.com/
 * @介紹：一個致力於幫助開發者用代碼改變世界為使命的平臺，每天都可以在這裡找到技術世界的頭條內容
 * @param {string} s
 * @return {number}
 */
var romanToInt = function(s) {
  let hash={
      I:1,
      V:5,
      X:10,
      L:50,
      C:100,
      D:500,
      M:1000
  }
  let sum=0
  for(let i=0;i<s.length;i++){
    let res
    let cur=hash[s[i]]
    let next=hash[s[i+1]]
    if(next  && cur < next){
      res=next-cur
      i++
    }else{
      res=cur
    }
    sum+=res
  }
  return sum
};
/**
 * @param {number} num
 * @return {string}
 //作者：Alexer-660
//連結：https://leetcode-cn.com/problems/integer-to-roman/solution/12-zheng-shu-zhuan-luo-ma-shu-zi-by-alexer-660/
 */
var romanToInt = function(s) {
    var hashNum = {
        "I":1,
        "V":5,
        "X":10,
        "L":50,
        "C":100,
        "D":500,
        "M":1000
    }
    var result = 0;
    for(let i = 0;i<s.length;i++){
        hashNum[s[i]] < hashNum[s[i+1]] ? result -= hashNum[s[i]] : result += hashNum[s[i]]
    }
    return result;
};
/**
 作者：iamapig120
連結：https://leetcode-cn.com/problems/integer-to-roman/solution/cyu-yan-js-cong-di-wei-kai-shi-an-wei-qu-zhi-cha-b/
 */
 /**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function(s) {
    let keys = ['M', 'CM', 'D', 'CD', 'C', 'XC', 'L', 'XL', 'X', 'IX', 'V', 'IV', 'I'],
        values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1],
        res = 0, idx;
    while(s.length) {
        idx = keys.indexOf(s[0] + s[1]);//先判斷是不是符合2個字符的單位
        if(idx >= 0){
            s = s.substring(2, s.length);
        }else{
            idx = keys.indexOf(s[0]);
            s = s.substring(1, s.length);
        }
        res += values[idx];//得到對應的值
    }
    return res;
};


c++ 實現
//作者：iamapig120
//連結：https://leetcode-cn.com/problems/integer-to-roman/solution/cyu-yan-js-cong-di-wei-kai-shi-an-wei-qu-zhi-cha-b/
class Solution {
public:
    int change(char a) {
        switch(a)
        {
            case 'I':return 1;break;
            case 'V':return 5;break;
            case 'X':return 10;break;
            case 'L':return 50;break;
            case 'C':return 100;break;
            case 'D':return 500;break;
            case 'M':return 1000;break;
        }
        return 0;
    }
    int romanToInt(string s) {
        int SUM=0,sum=0;
        int i;
        for(i=0;i<s.length();i++)
        {
            int num=change(s[i]);
            if(change(s[i+1])>num)num=-num;
            SUM+=num;
        }
        return SUM;
    }
};


// 作者：junex233
// 連結：https://leetcode-cn.com/problems/roman-to-integer/solution/si-lu-qing-xi-shi-xian-jian-dan-de-fang-fa-by-june/
class Solution {
public:
    int romanToInt(string s) {
        int result=0;
        map<char,int> luomab={
            {'I',1},
            {'V',5},
            {'X',10},
            {'L',50},
            {'C',100},
            {'D', 500},
            {'M', 1000}
        };//初始化哈希表
        for(int i=0;i<s.length();i++)
        {
            if(luomab[s[i]] < luomab[s[i+1]])
                result -= luomab[s[i]];
            else
            {
                result += luomab[s[i]];
            }
        }
        return result;
    }
};

python 實現
# 作者：z1m
# 連結：https://leetcode-cn.com/problems/roman-to-integer/solution/qing-xi-tu-jie-python3-by-ml-zimingmeng/
class Solution:
    def romanToInt(self, s: str) -> int:
        Roman2Int = {'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
        Int = 0
        n = len(s)

        for index in range(n - 1):
            if Roman2Int[s[index]] < Roman2Int[s[index + 1]]:
                Int -= Roman2Int[s[index]]
            else:
                Int += Roman2Int[s[index]]

        return Int + Roman2Int[s[-1]]



# 作者：zkk-c
# 連結：https://leetcode-cn.com/problems/integer-to-roman/solution/tan-xin-ha-xi-biao-tu-jie-by-ml-zimingmeng/
class Solution:
    def romanToInt(self, s: str) -> int:
#時間複雜度為O(n),空間複雜度為O(1)
        d = {'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000}
        result = 0
        for i in range(len(s) - 1):
            if d[s[i]] >= d[s[i + 1]]:
                result += d[s[i]]
            else:
                result -= d[s[i]]
        result += d[s[-1]]
        return result

其他原題leetcode連結：https://leetcode-cn.com/problems/roman-to-integer/合作方：JavaScript中文網 – 全球極客摯愛的技術成長平臺說明：leetcode 題解 | 每日一題🔥 所有題目並非全部為本人解答，部分為在複習學習中整理提取其他解題作者的優秀筆記，便於大家學習共同進步，如有侵權，請聯繫刪除。

相關焦點

  • 整數轉羅馬數字 | Leetcode題解
    題目描述:羅馬數字包含以下七種字符：I ， V ， X ， L ， C ， D 和 M 。通常情況下，羅馬數字中小的數字在大的數字的右邊。但也存在特例，例如 4 不寫做 IIII ，而是 IV 。數字 1 在數字 5 的左邊，所表示的數等於大數 5 減小數 1 得到的數值 4 。同樣地，數字 9 表示為 IX 。
  • 整數反轉 | Leetcode題解
    ，你需要將這個整數中每位上的數字進行反轉。請根據這個假設，如果反轉後整數溢出那麼就返回 0。難度：支持語言：JavaScript、Java、Python相關標籤相關企業思路 1:使用字符串在反轉並不是最好的選擇，因為還需要處理負號和0的情況，用數字運算方式反轉比較適合。
  • LeetCode刷題筆記 - 12. 整數轉羅馬數字
    官方連結：https://leetcode-cn.com/problemset/all/一、題意 難度：中等https://leetcode-cn.com/problems/integer-to-roman/羅馬數字包含以下七種字符
  • 每日一道算法:羅馬數字轉整數
    通常情況下，羅馬數字中小的數字在大的數字的右邊。但也存在特例，例如 4 不寫做 IIII，而是 IV。數字 1 在數字 5 的左邊，所表示的數等於大數 5 減小數 1 得到的數值 4 。同樣地，數字 9 表示為 IX。
  • 大廠筆試題——LeetCode12整數轉羅馬數字
    整數轉羅馬數字如果感覺不錯，歡迎關注、點讚、分享！長期堅持分享！題目描述：羅馬數字包含以下七種字符例如， 羅馬數字 2 寫做 II ，即為兩個並列的 1。通常情況下，羅馬數字中小的數字在大的數字的右邊。但也存在特例，例如 4 不寫做 IIII，而是 IV。數字 1 在數字 5 的左邊，所表示的數等於大數 5 減小數 1 得到的數值 4 。同樣地，數字 9 表示為 IX。
  • 發現規律,解決整數轉羅馬數字
    羅馬數字包含以下七種字符：I， V， X， L，C，D 和 M。 字符數值I1V5X10L50C100D500M100027 寫做  XXVII, 即為 XX + V + II 。通常情況下，羅馬數字中小的數字在大的數字的右邊。
  • 經典面試題:整數和羅馬數字互轉(上集)
    整數轉羅馬數字」，難度為 Medium。羅馬數字包含以下七種字符：I， V， X， L，C，D 和 M。通常情況下，羅馬數字中小的數字在大的數字的右邊。但也存在特例，例如 4 不寫做 IIII，而是 IV。數字 1 在數字 5 的左邊，所表示的數等於大數 5 減小數 1 得到的數值 4 。同樣地，數字 9 表示為 IX。
  • LeetCode-7. Reverse Integer | 整數反轉
    123Output: 321Example 2:Input: x = -123Output: -321Example 3:Input: x = 120Output: 21Example 4:Input: x = 0Output: 0Constraints:-231 <= x <= 231 - 1題解通過題目可以看出來，這道題是讓我們翻轉一個整數
  • LeetCode Weekly Contest 204 題解
    /blob/master/LeetCode/leetcode_detect-pattern-of-length-m-repeated-k-or-more-times.cpp題解：模擬或者是單純的數組題。
  • LeetCode Weekly Contest 224 題解
    --InterviewProblem/blob/master/LeetCode/leetcode_number-of-rectangles-that-can-form-the-largest-square.cpp題解：模擬題。
  • [簡單]羅馬數字轉整數
    題目羅馬數字包含以下七種字符: I， V， X， L，C，D 和 M。
  • 笨方法刷 leetcode(一)
    最近在看leetcode，並且正在上面刷一些簡單級別的題目（不過說真的，這些題真的簡單嗎？？示例:  給定 nums = [2, 7, 11, 15], target = 9  因為 nums[0] + nums[1] = 2 + 7 = 9 原題連結：https://leetcode-cn.com/problems/two-sum/解決思路：用第1個數字依次與其後面的數字相加
  • 每日一道 LeetCode (2):整數反轉
    題目：整數反轉題目來源：https://leetcode-cn.com/problems/reverse-integer
  • 推薦4個基於 Java語言的開源 Leetcode 題解!算法面試不愁了!
    為了能夠幫助我們更好的刷 Leetcode，Guide 精選了一些不錯的基於 Java 題解的開源項目，文末有項目連結。下面的項目是根據下面三個標準選出：項目的質量如何，這一點可以從 star、issue 以及 pr 的數量側面反映出來。
  • LeetCode刷題實戰8:字符串轉換整數
    if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.If no valid conversion could be performed, a zero value is returned.https://leetcode-cn.com
  • 三數之和 | Leetcode題解
    題目描述給你一個包含 n 個整數的數組 nums，判斷 nums 中是否存在三個元素 _a，b，c ，_使得 a + b + c = 0 ？請你找出所有滿足條件且不重複的三元組。**注意：**答案中不可以包含重複的三元組。
  • LeetCode刷題實戰7:整數反轉
    今天和大家聊的問題叫做 整數反轉  ，這道題很有意思，我們先來看題面：題意Given a 32-bit signed integer, reverse digits of an integer.https://leetcode.com/problems/reverse-integer/
  • leetcode-cheatsheet 史詩級更新,來看看我是如何寫題解的
    ，插件現在內置題解模板功能，目前模板只有一套，這套模板是「我經常使用的題解模板」。最後祝大家寫出漂亮的題解！體驗優化「路由」記憶現在增加「路由」記憶功能。比如上面提到的「寫題解」功能，當你點擊寫題解按鈕後，會「自動定位到題解模板標籤頁」網站寬度調整之前考慮的僅僅是插件中使用，而現在除了在插件中運行，還可以在 PC 端運行。因此我增加了一個打包命令專門用來打包到 「PC 端」。
  • LeetCode(7-整數反轉&&8-字符串轉換整數 (atoi)&&9-迴文數)
    這是今年LeetCode60題的第三篇題解,已完成目標的15%.如果覺得UP寫的不錯的話,可以點擊上方藍字關注哦,後續會持續更新LeetCode題解.整數反轉「題目描述」:給你一個 32 位的有符號整數 x ，返回 x 中每位上的數字反轉後的結果。如果反轉後整數超過 32 位的有符號整數的範圍 [−231,  231 − 1] ，就返回 0。假設環境不允許存儲 64 位整數（有符號或無符號）。
  • Leetcode刷題-字符串
    整數轉羅馬數字難度：中等羅馬數字包含以下七種字符：I， V， X， L，C，D 和 M。通常情況下，羅馬數字中小的數字在大的數字的右邊。但也存在特例，例如 4 不寫做 IIII，而是 IV。數字 1 在數字 5 的左邊，所表示的數等於大數 5 減小數 1 得到的數值 4 。同樣地，數字 9 表示為 IX。這個特殊的規則只適用於以下六種情況：I 可以放在 V (5) 和 X (10) 的左邊，來表示 4 和 9。