7-罗马数字转整数

题目

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

字符	数值
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

• I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。

• X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。

• C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。

示例 1:

输入: "III" 输出: 3

示例 2:

输入: "IV" 输出: 4

示例 3:

输入: "IX" 输出: 9

示例 4:

输入: "LVIII" 输出: 58 解释: L = 50, V= 5, III = 3.

示例 5:

输入: "MCMXCIV" 输出: 1994 解释: M = 1000, CM = 900, XC = 90, IV = 4.

解答

先暴力破解再说

思路就是照着规则做咯 一个个字符，翻译成数字，相加。遇到特殊情况，再另做打算。

/**
 * @param {string} s
 * @return {number}
 */
const TO_INT_MAP = {
  I: 1,
  V: 5,
  X: 10,
  L: 50,
  C: 100,
  D: 500,
  M: 1000
};

var romanToInt = function(s) {
  let number = 0;
  for (let i = 0; i < s.length; i++) {
    const element = s[i];
    const numb = TO_INT_MAP[element];
    if (s[i - 1]) {
      if (s[i - 1] === "I" && (numb === 5 || numb === 10)) {
        number -= 2;
      } else if (s[i - 1] === "X" && (numb === 50 || numb === 100)) {
        number -= 20;
      } else if (s[i - 1] === "C" && (numb === 500 || numb === 1000)) {
        number -= 200;
      }
    }
    number += numb;
  }
  return number;
};

Runtime: 124 ms, faster than 98.85% of JavaScript online submissions forRoman to Integer.

Memory Usage: 40.4 MB, less than 26.42% of JavaScript online submissions for Roman to Integer.

优化一下？

每次都要判断一下s[i-1]是否存在，感觉没必要。 number初始化就能是第一个值，接下来的就不用判断了。

var romanToInt = function(s) {
  let number = TO_INT_MAP[s[0]];                 // 初始化就是第一个值
  for (let i = 1; i < s.length; i++) {  // i从1开始
    ...
  }
...
};

Runtime: 144 ms, faster than 80.32% of JavaScript online submissions forRoman to Integer.

Memory Usage: 40.1 MB, less than 36.61% of JavaScript online submissions for Roman to Integer.

好像消耗的内存少了，但花费的时间增加了。

翻译的时候优先两两翻译

作者：guanpengchn 链接：https://leetcode-cn.com/problems/two-sum/solution/hua-jie-suan-fa-13-luo-ma-shu-zi-zhuan-zheng-shu-b/

把所有可能的情况都列出来，然后优先两两翻译，没有就一个个翻译

const TO_INT_MAP = {        // 列出了所有的情况
  I: 1,
  IV: 4,
  V: 5,
  IX: 9,
  X: 10,
  XL: 40,
  L: 50,
  XC: 90,
  C: 100,
  CD: 400,
  D: 500,
  CM: 900,
  M: 1000
};

var romanToInt = function(s) {
  let number = 0;
  for (let i = 0; i < s.length; ) {
    if (i + 1 < s.length && TO_INT_MAP[s.substring(i, i + 2)]) { // 切片
      number += TO_INT_MAP[s.substring(i, i + 2)];
      i += 2;
    } else {
      number += TO_INT_MAP[s.substring(i, i + 1)];
      i += 1;
    }
  }
  return number;
};

Runtime: 148 ms, faster than 75.12% of JavaScript online submissions forRoman to Integer.

Memory Usage: 39.8 MB, less than 69.57% of JavaScript online submissions for Roman to Integer.

substring的作用感觉类似于slice，那有啥区别呢这两者？

var romanToInt = function(s) {
...
    if (i + 1 < s.length && TO_INT_MAP[s.slice(i, i + 2)]) {
      number += TO_INT_MAP[s.slice(i, i + 2)];
...
    } else {
      number += TO_INT_MAP[s.slice(i, i + 1)];
...
    }
  }
...
};

Runtime: 136 ms, faster than 91.66% of JavaScript online submissions forRoman to Integer.

Memory Usage: 40 MB, less than 46.84% of JavaScript online submissions for Roman to Integer.

似乎slice更快一些，也更耗内存一些？

这篇文章里面介绍了一下主要的区别。我的理解是这样的：

slice和substring大体上是一样的，主要区别在于对负数的处理。

• slice中的负数，起点最后一位字符。

• substring中的负数，起点第一位字符。

var str = 'abcdefghij';

str.slice(-2);        // 'ij'
// 从index = str.length - 2 开始切，也就留下了最后两个字符
str.substring(-2);    // 'abcdefghij' 
// 从index=-2开始切，自然没有字符，就从0开始切

str.slice(-3, -1); // 'hi'
str.substring(-3, -1); // ''  // 因为根本没字符串

还有个区别，就是substring更加瓷实一些。

str.substring(5, 1); // 'bcde' // 自动反转两个输入值
str.slice(5, 1); // ''  // slice: 你输入的啥我看不懂？

其他的区别可能就在性能上了，那我就不太懂了。

双指针

不记录所有的情况，而是保留上一个指针的值。 如果小了，那么就说明需要减一下了。

const TO_INT_MAP = {
  I: 1,
  V: 5,
  X: 10,
  L: 50,
  C: 100,
  D: 500,
  M: 1000
};

var romanToInt = function(s) {
  let number = 0;
  let preNumb = 10000;
  for (let i = 0; i < s.length; i++) {
    const numb = TO_INT_MAP[s[i]];
    number += numb;
    if (preNumb < numb) {            // 如果之前值比现在要小，那么就要减掉两倍的之前值
      number -= 2 * preNumb;
    }
    preNumb = numb;
  }
  return number;
};

Runtime: 164 ms, faster than 56.31% of JavaScript online submissions forRoman to Integer.

Memory Usage: 39.5 MB, less than 93.46% of JavaScript online submissions for Roman to Integer.

虽然也能做出来，但我总觉得有问题 因为“减法”的特殊规则只有这6条，如果输入的是IL呢？

双指针的做法，算出来的是49，而其他方法，算出来的是51

那么结果应该是多少呢？

我觉得，现实中应该是49，不过本题之中，应该是51——因为IL不在特殊规则之内啊。