Shinkai005
V1
2022/01/16阅读:62主题:红绯
# 【leetcode】13.罗马数字转整数
【leetcode】13.罗马数字转整数.md
题目描述
题目思路
-
暴力法 -
遇到vi iv 直接转换成其他字母,然后给返回值不就好? -
如果不想把 vi iv 这种转换成单字母怎么办?
-
-
对罗马数字还有另一层解释 -
通常情况下,罗马数字中小的数字在大的数字的右边。若输入的字符串满足该情况,那么可以将每个字符视作一个单独的值,累加每个字符对应的数值即可。
-
个人题解
暴力法:
/**
* @param {string} s
* @return {number}
*/
var romanToInt = function(s) {
// 暴力解法
s = s.replace("IV","a");
s = s.replace("IX","b");
s = s.replace("XL","c");
s = s.replace("XC","d");
s = s.replace("CD","e");
s = s.replace("CM","f");
let res = 0;
for (let i = 0; i < s.length; i++) {
res += getValue(s.charAt(i));
}
return res;
}
const getValue= (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;
case 'a': return 4;
case 'b': return 9;
case 'c': return 40;
case 'd': return 90;
case 'e': return 400;
case 'f': return 900;
}
return false;
}
时间复杂度:
用到了string的replace方法,取决于实现方式.感兴趣看看v8怎么实现的.但是肯定不是o(1),因为我用了这个所以时间复杂度较高.'
后面有个for循环 n量级 因此 最快估计也在O(n+logn) 也就是O(n) logn是二分查找的速度.
空间复杂度:
O(1)
暴力法第二种方式
这个比较复杂,但是我刚开始也是想着用这种方式
**
* @param {string} s
* @return {number}
*/
var romanToInt = function(s) {
let map = new Map([['I',1], ['V',5], ['X',10], ['L',50], ['C',100], ['D',500], ['M',1000],
['IV',4], ['IX',9], ['XL',40], ['XC',90], ['CD',400], ['CM',900]]
) // 利用Map存储罗马数字与对应值得映射关系
let sum = 0;
for(let i=0; i<s.length;) {
if(s.length && map.has(s.substring(i, i+2))) { // 检查map里面是否存在连续的两个罗马数字
sum += map.get(s.substring(i, i+2));
i+=2;
}else { // 假如map里面没有连续的两个罗马数字
sum += map.get(s.substring(i, i+1));
i++;
}
}
return sum // 共用了sum
};
其他题解
这个就是利用了小数字一般在大数字右边,左边的话就被减去.
var romanToInt = function(s) {
const map = new Map([['I', 1],['V', 5],['X', 10],['L', 50],['C', 100],['D', 500],['M', 1000]]);
let res = 0;
for (let i = 0; i < s.length; ++i) {
const value = map.get(s[i]);
if (i < s.length - 1 && value < map.get(s[i + 1])) {
//防止破界,要判断i和长度关系
res -= value;
} else {
//最后一个值永远加
res += value;
}
}
return res;
};
这个速度就非常快...,但是为啥比上面的replace,同复杂度的,快这么多...
有趣的解法
“这才叫暴力解法,我写的不够暴力..,而且这个速度巨快..空间复杂度也巨低..服了
”
/**
* @param {string} s
* @return {number}
*/
var romanToInt = function(s) {
const n = s.length;
let i = 0;
let res = 0;
while(i < n) {
if (s[i] === 'M') {
res += 1000;
i++;
} else if (s[i] === 'C' && s[i+1] === 'M') {
res += 900;
i += 2;
} else if (s[i] === 'D') {
res += 500;
i++;
} else if (s[i] === 'C' && s[i+1] === 'D') {
res += 400;
i += 2;
} else if (s[i] === 'C') {
res += 100;
i++;
} else if (s[i] === 'X' && s[i+1] === 'C') {
res += 90;
i += 2;
} else if (s[i] === 'L') {
res += 50;
i++;
} else if (s[i] === 'X' && s[i+1] === 'L') {
res += 40;
i += 2;
} else if (s[i] === 'X') {
res += 10;
i++;
} else if (s[i] === 'I' && s[i+1] === 'X') {
res += 9;
i += 2;
} else if (s[i] === 'V') {
res += 5;
i++;
} else if (s[i] === 'I' && s[i+1] === 'V') {
res += 4;
i += 2;
} else if (s[i] === 'I') {
res += 1;
i++;
}
}
return res;
};
作者介绍
Shinkai005
V1
公众号:深海笔记Shinkai