Leetcode 13ローマ数字回転整数
1857 ワード
ローマ数字には、I、V、X、L、C、D、Mの7文字が含まれています.文字値I 1 V 5 X 10 L 50 C 100 D 500 M 1000は、例えば、ローマ数字2をIIと書くと、2つの並列の1となる.12はXIIと書きます.つまりX+IIです.27 XXVIIと書くと、XX+V+IIとなります.通常、ローマ数字の中で小さい数字は大きな数字の右側にあります.しかし、例えば4はIIIではなくIVと書くという特例もある.数字1は数字5の左側にあり、表す数は大数5から小数1を減らした数値4に等しい.同様に、数字9はIXとして表される.この特殊な規則は以下の6つの場合にのみ適用される: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.
構想:同12題.しかし、ここで難しい点はIV、IXの値について、どのようにマッピングするかです.直接ビットで1文字をマッチングするのはだめです.まず2文字をマッチングしてから1文字をマッチングしてみましょう.問題の配列を使ってループするのは時間の制限を超えます.だから、ここではhashmapを使いました.彼の検索はO(1)です.
例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.
構想:同12題.しかし、ここで難しい点はIV、IXの値について、どのようにマッピングするかです.直接ビットで1文字をマッチングするのはだめです.まず2文字をマッチングしてから1文字をマッチングしてみましょう.問題の配列を使ってループするのは時間の制限を超えます.だから、ここではhashmapを使いました.彼の検索はO(1)です.
class Solution {
public int romanToInt(String s) {
int ans = 0;
HashMap map = new HashMap();
map.put("CM",900);map.put("CD",400);map.put("XC",90);
map.put("XL",40);map.put("IX",9);map.put("IV",4);
map.put("M",1000);map.put("D",500);map.put("C",100);
map.put("L",50);map.put("X",10);map.put("V",5);map.put("I",1);
String temp = s;
while(temp.length()>0){
int i = 0;
if(temp.length()>1&&map.containsKey(temp.substring(i,i+2))){
ans = map.get(temp.substring(i,i+2)) + ans;
temp = temp.substring(i+2,temp.length());
continue;
}else if(temp.length()>0&&map.containsKey(temp.substring(i,i+1))){
ans = ans + map.get(temp.substring(i,i+1));
temp = temp.substring(i+1,temp.length());
continue;
}
}
return ans;
}
}