天天看點

LeetCode_字元串_中等_13.羅馬數字轉整數1.題目2.思路3.代碼實作(Java)

目錄

  • 1.題目
  • 2.思路
  • 3.代碼實作(Java)

1.題目

羅馬數字包含以下七種字元: 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

提示:

1 <= s.length <= 15

s 僅含字元 (‘I’, ‘V’, ‘X’, ‘L’, ‘C’, ‘D’, ‘M’)

題目資料保證 s 是一個有效的羅馬數字,且表示整數在範圍 [1, 3999] 内

題目所給測試用例皆符合羅馬數字書寫規則,不會出現跨位等情況。

IL 和 IM 這樣的例子并不符合題目要求,49 應該寫作 XLIX,999 應該寫作 CMXCIX 。

來源:力扣(LeetCode)

連結:https://leetcode-cn.com/problems/roman-to-integer

2.思路

(1)與專欄LeetCode算法刷題中的第12題整數轉羅馬數字的思路1類似,先将羅馬數字與對應的整數的映射關系存儲起來,然後周遊給出的羅馬數字,不過在周遊時需要考慮到一次周遊一個字元和一次周遊兩個字元這兩種情況。

3.代碼實作(Java)

//(1)思路1
public int romanToInt(String s) {
    int res=0;
    Map<String, Integer> map = new HashMap<>();
    map.put("I", 1);
    map.put("IV", 4);
    map.put("V", 5);
    map.put("IX", 9);
    map.put("X", 10);
    map.put("XL", 40);
    map.put("L", 50);
    map.put("XC", 90);
    map.put("C", 100);
    map.put("CD", 400);
    map.put("D", 500);
    map.put("CM", 900);
    map.put("M", 1000);
    for(int i=0;i<s.length();){
        if(i+2<=s.length() && map.containsKey(s.substring(i,i+2))){
            res+=map.get(s.substring(i,i+2));
            i+=2;
        }else if(i+1<=s.length() && map.containsKey(s.substring(i,i+1))){
            res+=map.get(s.substring(i,i+1));
            i++;
        }
    }
    return res;
}