題目描述
羅馬數字包含以下七種字符：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 寫做 X 雙 VII，即為 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. 將String轉為char陣列
2. 定義int變數num作為return的變數
3. 干擾正常計數的情況只有IV、IX、XL、XC、CD、CM六種，所以我們遍歷char陣列，注意這次遍歷從i = 0到i = ch.length - 1，因為要判斷ch[i+1]
4. 判斷ch[i] 和 ch[i+1]的情況，假如滿足IV或者IX，就把num-2，因為IV=4，比起正常的I + V要減少2，依次類推，碰到XL、XC需要num-20，碰到CD、CM需要num-200
5. 再次遍歷陣列，這回就只需要判斷字母是什么，把num加上對應的值，例如 ch[i] = C; num += 100;
class Solution {
public int romanToInt(String s) {
//將String轉為char陣列
char[] ch = s.toCharArray();
//定義int遍歷num作為return的變數
int num = 0;
//干擾正常計數的情況只有IV、IX、XL、XC、CD、CM 六種，所以我們遍歷char陣列，注意這次遍歷從i到i=ch.length-1,因為要判斷ch[i+1]
for (int i = 0; i < ch.length - 1; i++) {
//判斷ch[i]和ch[i+1]的情況，假如滿足IV或者IX，就把num-2，因為IV=4，比起正常的I + V 要減少2，一次類推，碰到XL，XC需要num-20，碰到CD、CM需要num-200
if(ch[i] == 'I' && (ch[i + 1] == 'V' || ch[i + 1] == 'X'))
num -= 2;
if(ch[i] == 'X' && (ch[i + 1] == 'L' || ch[i + 1] == 'C'))
num -= 20;
if(ch[i] == 'C' && (ch[i + 1] == 'D' || ch[i + 1] == 'M'))
num -= 200;
}
//再次遍歷陣列，這回只需要判斷字母是什么，num加上對應的值，例如ch[i]=M; num+=1000;
for (int i = 0; i < ch.length; i++) {
switch (ch[i]) {
case 'M': {
num += 1000;
continue;
}
case 'D': {
num += 500;
continue;
}
case 'C': {
num += 100;
continue;
}
case 'L': {
num += 50;
continue;
}
case 'X': {
num += 10;
continue;
}
case 'V': {
num += 5;
continue;
}
default: {
num += 1;
continue;
}
}
}
return num;
}
方法二:hash表
思路
- 首先將所有的組合可能性列出并添加到哈希表中
- 然后對字串進行遍歷，由于組合只有兩種，一種是 1 個字符，一種是 2 個字符，其中 2 個字符優先于 1 個字符
- 先判斷兩個字符的組合在哈希表中是否存在，存在則將值取出加到結果 ans 中，并向后移2個字符，不存在則將判斷當前 1 個字符是否存在，存在則將值取出加到結果 ans 中，并向后移 1 個字符
- 遍歷結束回傳結果 ans
代碼實作
class Solution {
public int romanToInt(String s) {
//將所有的組合可能性列出并添加到哈希表中
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);
//定義答案變數
int ans = 0;
for(int i = 0;i < s.length();) {
//如果i+1小于字串總長度并且字串中當前第i到i+2這兩個羅馬字符是否在map里，如果不在則是一個羅馬字符
if(i + 1 < s.length() && map.containsKey(s.substring(i, i+2))) {
//把兩個羅馬字符加到ans答案里
ans += map.get(s.substring(i, i+2));
//找到兩個羅馬字符，i則后移兩位
i += 2;
} else {
//把一個羅馬字符加到ans答案里
ans += map.get(s.substring(i, i+1));
//找到一個羅馬字符，i則后移一位
i ++;
}
}
return ans;
}
}
知識擴展
【知識卡片】哈希表存盤的是由鍵（key）和值（value）組成的資料，例如，我們將每個人的性別作為資料進行存盤，鍵為人名，值為對應的性別，
- Python 中我們使用字典key:value}來初始化哈希表
- 通過key查找value的時間復雜度為O（1）
- 這題題解中的d就是一個字典，其中get（key，default）函式可以通過key從d中找出對應的值，如果key不存在則回傳默認值 default
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/116913.html
標籤：其他
上一篇：動態規劃演算法詳解及經典例題
下一篇：單網卡雙IP設定問題