面试经典150题——罗马数字转整数

embedded/2024/10/18 14:25:04/

面试经典150题 day17

- - 题目来源
  - 我的题解
  - - 方法一哈希表
    - 方法二优化版本

题目来源

力扣每日一题；题序：13

我的题解

方法一哈希表

存储单独的存在的可能字符串

时间复杂度：O(n)
空间复杂度：O©。C表示单独存在的可能字符串数量

java">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 res=0;for(int i=0;i<s.length();){if(i<s.length()-1&&map.containsKey(s.substring(i,i+2))){res+=map.get(s.substring(i,i+2));i+=2;}else{int cur=map.get(s.substring(i,i+1));res+=cur;i++;}}return res;
}

方法二优化版本

实际存储map时不需要存储String类型，方法一为了存储像“IV”、“VX”这种比较特别的值，导致需要使用String来存储。方法二不再存储特殊的值，因此转为使用Character类型进行存储。只需要判断s中相邻两个字符对应的值的差是否是4或者9的倍数，若后一个字符的数字值大于前一个字符的数字值，并且差值是4或者9的倍数，这两个相邻的字符将组成一个罗马数字。

时间复杂度：O(n)
空间复杂度：O(K)。

java">public int romanToInt(String s) {Map<Character,Integer> 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 res=0;char[] data=s.toCharArray();int i=0;for(;i<data.length-1;i++){int num1=map.get(data[i]);int num2=map.get(data[i+1]);if((num2-num1)>0&&((num2-num1)%4==0||(num2-num1)%9==0)){res+=num2-num1;i++;}else{res+=num1;}}if(i==data.length-1)res+=map.get(data[i]);return res;
}