首页 > itarticle > algorithm notes: leetcode#13 roman to integer

algorithm notes: leetcode#13 roman to integer

admin 11月 12, 2020 0

Problem

Solution

Initial thoughts

Python implementation

class :
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        hash_map = {
            'I' : 1,
            'V' : 5,
            'X' : 10,
            'L' : 50,
            'C' : 100,
            'D' : 500,
            'M' : 1000
        }
        
        nums = [hash_map[c] for c in s]
        ans = nums[-1]
        for i in range(1, len(s)):
            if nums[-i-1] < nums[-i] :
                ans -= nums[-1-i]
            else:
                ans += nums[-1-i]
        return ans

Java implementation

class  {
    public int romanToInt(String s) {
        char[] chars = {'I', 'V', 'X', 'L', 'C', 'D', 'M'};
        int[] vals = {1, 5, 10, 50, 100, 500, 1000};
        Map<Character, Integer> hashMap = new HashMap<>();
        for(int i = 0; i < vals.length; i++){ hashMap.put(chars[i], vals[i]); }
        
        int i = 0;
        int[] nums = new int[s.length()];
        for(char c : s.toCharArray()){
            nums[i++] = hashMap.get(c);
        }
        
        int ans = nums[s.length() - 1];
        int l = s.length();
        
        for(i = 1; i < l; i++){
            if(nums[l-i-1] < nums[l-i]){
                ans -= nums[l-1-i];
            }else{
                ans += nums[l-1-i];
            }
        }
        
        return ans;
    }
}

Time complexity

O(N).

Space complexity

O(N).

Links

13. Roman to Integer
(中文版) 算法笔记: 力扣#13 罗马数字转整数