執行用時：2 ms, 在所有 Java 提交中擊敗了100.00%的用戶
題目
https://leetcode-cn.com/problems/roman-to-integer
羅馬數字包含以下七種字符: 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， 給定一個羅馬數字，將其轉換成整數，
解題思路
對字串進行遍歷，每次遍歷取一個字符c和下一個字符next：
如果c和next是IV這種組合，就減去I的值再加上V的值，然后i++跳過next，否則就直接加上c的值，
這種方法的好處是，保證了每一個字符只會被掃描一次
速度快核心可能是減少各種判斷，全部用if - else -_-||
代碼
class Solution {
private static int getBaseValue(char c) {
switch (c) {
case 'I':
return 1;
case 'V':
return 5;
case 'X':
return 10;
case 'L':
return 50;
case 'C':
return 100;
case 'D':
return 500;
case 'M':
return 1000;
}
return 0;
}
public int romanToInt(String s) {
int result = 0;
for (int i = 0; i < s.length(); i += 1) {
char c = s.charAt(i);
if (i + 1 == s.length()) {
return result + getBaseValue(c);
}
char next = s.charAt(i + 1);
if
(
(c == 'I' && (next == 'V' || next == 'X'))
|| (c == 'X' && (next == 'L' || next == 'C'))
|| (c == 'C' && (next == 'D' || next == 'M'))
){
i++;
result-=getBaseValue(c);
result+=getBaseValue(next);
}else{
result+=getBaseValue(c);
}
}
return result;
}
}
復雜度分析
-
時間復雜度：O(n)
-
空間復雜度：O(1)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/458393.html
標籤：其他
上一篇：電腦微信中快捷鍵的秘密——聊聊那些你知道的和不知道的微信快捷鍵
下一篇：UE4 C++呼叫手柄震動