【leetcode】13.罗马数字转整数.md

题目描述

题目思路

1. 暴力法

   1. 遇到vi iv 直接转换成其他字母,然后给返回值不就好?
   2. 如果不想把 vi iv 这种转换成单字母怎么办?
2. 对罗马数字还有另一层解释

   1. 通常情况下，罗马数字中小的数字在大的数字的右边。若输入的字符串满足该情况，那么可以将每个字符视作一个单独的值，累加每个字符对应的数值即可。

个人题解

暴力法:

/**
 * @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;
};