leetcode:13.羅馬數字轉整數

題目描述：

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

題目難度：簡單

分析：

這題是把上一題的輸入和輸出倒了過來，這樣的話其實比上一題還簡單。直接周遊字元串即可。

代碼如下：

class Solution {
    public int romanToInt(String s) {
    	// 定義一個傳回結果
        int count = 0;
        // 周遊字元串
        for (int i = 0; i < s.length(); i++) {
        	// 目前的臨時字元
            char temp = s.charAt(i);
            // 下一個字元
            char tempNext = '-';
            // 判斷是否是最後一個
            if (i + 1 < s.length()) {
                tempNext = s.charAt(i + 1);
            }
            // 分别判斷目前字元是屬于7種字元中的哪一種
            if ('I' == temp) {
            	// 然後判斷下一個字元是否能和目前字元組合
                if ('V' == tempNext) {
                	// 加上相應的數字即可
                    count += 4;
                    i++;
                } else if ('X' == tempNext) {
                    count += 9;
                    i++;
                } else {
                    count += 1;
                }
            // 以此類推......
            } else if ('V' == temp) {
                count += 5;
            } else if ('X' == temp) {
                if ('L' == tempNext) {
                    count += 40;
                    i++;
                } else if ('C' == tempNext) {
                    count += 90;
                    i++;
                } else {
                    count += 10;
                }
            } else if ('L' == temp) {
                count += 50;
            } else if ('C' == temp) {
                if ('D' == tempNext) {
                    count += 400;
                    i++;
                } else if ('M' == tempNext) {
                    count += 900;
                    i++;
                } else {
                    count += 100;
                }
            } else if ('D' == temp) {
                count += 500;
            } else {
                count += 1000;
            }
        }
        return count;
    }
}
           

總結：

時間複雜度為 O ( l o g 10 n ) O(log_{10}n) O(log10​n)，雖然看起來很麻煩，不過效率高，隻需要一次周遊即可。也可以用switch代替if。