leetcode07-罗马数字的转换
题目链接:
https://leetcode.cn/problems/roman-to-integer/?envType=study-plan-v2&envId=programming-skills
思路:
将罗马数字与数值的映射关系先存在一个哈希表中;
对于罗马数字,若前一个罗马数字映射的值小于后一个所映射的值,则数值应该减去前一个罗马数字映射的数值,反之则加上。遍历字符串s,重复上述操作。
代码:
class Solution {public int romanToInt(String s) {//构建哈希表的映射关系Map<Character,Integer> map = new HashMap<Character,Integer>();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 sum = 0;//记录总和int n = s.length();int prevalue = map.get(s.charAt(0));for(int i = 1;i<n;i++){int value = map.get(s.charAt(i));if(prevalue<value) {sum-=prevalue;}else {sum+=prevalue;}prevalue = value;}sum+=prevalue;return sum;}
}
执行速度:5ms 内存占用:43.73MB
将哈希表的映射关系改为采用函数实现,可以大大减少执行速度
优化后的代码:
class Solution {public static int get(char c) {switch(c) {case 'I':return 1;case 'V':return 5;case 'X':return 10;case 'L':return 50;case 'C':return 100;case 'D':return 500;case 'M':return 1000;default:return 0;}
}public int romanToInt(String s) {//构建哈希表的映射关系int sum = 0;//记录总和int n = s.length();int prevalue = get(s.charAt(0));for(int i = 1;i<n;i++){int value = get(s.charAt(i));if(prevalue<value) {sum-=prevalue;}else {sum+=prevalue;}prevalue = value;}sum+=prevalue;return sum;}
}
执行速度: 2ms 占用内存:43.57MB