Categories
All 技術 算法

做題筆記:Roman to Integer (Java)

題目描述:

將羅馬數字轉換為整數,具體規則略。

Example 1:

Input: s = "III"
Output: 3
Explanation: III = 3.

Example 2:

Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 3:

Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

自己的 Switch 暴力解法:

兜了好幾個圈……

class Solution {
    public int romanToInt(String s) {
        int num = 0;
        StringBuilder re = new StringBuilder();
        re.append(s).reverse();
        String[] split = re.toString().split("(?<=\\G..)");
        for (String i:split){
            switch(i){
                case "VI":
                    num = num + 4;
                    break;
                case "XI":
                    num = num + 9;
                    break;
                case "LX":
                    num = num + 40; 
                    break;
                case "CX":
                    num = num + 90; 
                    break;
                case "DC":
                    num = num + 400;
                    break;
                case "MC":
                    num = num + 900; 
                    break;
                default:
                    String[] sub = i.split("");
                    for (String j:sub){
                        switch(j){
                            case "I":
                                num = num + 1;
                                break;
                            case "V":
                                num = num + 5;
                                break;
                            case "X":
                                num = num + 10; 
                                break;
                            case "L":
                                num = num + 50; 
                                break;
                            case "C":
                                num = num + 100;
                                break;
                            case "D":
                                num = num + 500; 
                                break;
                            case "M":
                                num = num + 1000;     
                                break;
                        }
                    }
                }
        }
        return num;    
    }
}

意外發生了,本地 IDE 能跑出正確答案,但是在 Leetcode 上跑不出來,我竟然為這種問題浪費了不少時間,最終也沒解決……

正確精練的 Switch 解法:

class Solution {
	 public int romanToInt(String s) {
	    int nums[] = new int[s.length()];
	    for(int i = 0; i < s.length(); i++){
	        switch (s.charAt(i)) {
	            case 'M':
	                nums[i] = 1000;
	                break;
	            case 'D':
	                nums[i] = 500;
	                break;
	            case 'C':
	                nums[i] = 100;
	                break;
	            case 'L':
	                nums[i] = 50;
	                break;
	            case 'X' :
	                nums[i] = 10;
	                break;
	            case 'V':
	                nums[i] = 5;
	                break;
	            case 'I':
	                nums[i] = 1;
	                break;
	        }
	    } 
	    
	    int sum = 0;
	    for(int i=0; i<nums.length-1; i++){
	        if(nums[i] < nums[i+1])
	            sum -= nums[i];
	        else
	            sum += nums[i];
	    }
         
	    return sum + nums[nums.length-1];
	}
}

6 ms

運用 Hashmap:

class solution {
    public int romanToInt(String s) {
        Map map = new HashMap<>();
        map.put('I',1);
        map.put('V',5);
        map.put('X',10);
        map.put('L',50);
        map.put('C',100);
        map.put('D',500);
        map.put('M',1000);
        
        int result = map.get(s.charAt(s.length()-1));
        for(int i=s.length()-2; i>=0; i--){
            if(map.get(s.charAt(i)) < map.get(s.charAt(i+1))){
                result -= map.get(s.charAt(i));
            }
            else{
                result += map.get(s.charAt(i));
            }
        }
        return result;
    }
}

Leave a Reply

Your email address will not be published.