问题描述
https://leetcode.com/problems/roman-to-integer/
解决思路(2019-07-03)
仔细分析罗马数字的技术方法，可以发现，如果不需要动用减法，则从右向左，依次变大；如果需要动用减法，则右边的会小于左边的。
- 用HashMap将罗马数字和阿拉伯数字建立键值关系
- 从后向前遍历给定字符串，如果前一位num大于后一位last，则sum加num；如果前一位num小于后一位，则sum减去num。
- 将num给last，继续进行下一轮循环。
代码
class Solution {
public int romanToInt(String s) {
//store symbol and value as K-V
HashMap<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 sum = map.get(s.charAt(s.length() - 1));
for(int i = s.length() - 2; i >= 0; i--){
//if the left symbol is less, do substraction
if(map.get(s.charAt(i)) < map.get(s.charAt(i + 1))){
sum -= map.get(s.charAt(i));
}else{
sum += map.get(s.charAt(i));
}
}
return sum;
}
}
解决思路(2019-12-01)
- the data structure should be hashMap
- traverse the string from right to left
- if right is less than left, so add left
- if right is more than left, so substract the left
代码
class Solution {
//0. the data structure should be hashMap
//1. traverse the string from right to left
//2. if right is less than left, so add left
//3. if right is more than left, so substract the left
public int romanToInt(String s) {
int len = s.length();
int leftValue = 0;
int rightValue = 0;
HashMap<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);
//add the last number first
int res = 0;
System.out.println(s.charAt(len - 1));
int a = map.get(s.charAt(len - 1));
System.out.println(a);
res += map.get(s.charAt(len - 1));
//traverse the string
for(int i = len - 2; i >= 0; i--){
//get the value of right and left
leftValue = map.get(s.charAt(i));
rightValue = map.get(s.charAt(i + 1));
//compare the right char with the left char
if(leftValue < rightValue){
res -= leftValue;
}else{
res += leftValue;
}
}
return res;
}
}
复杂度分析
时间复杂度: O(n)
空间复杂度: O(n)
