leetcode13：罗马数字转整数

给定一个罗马数字，将其转换成整数，多种思路实现

罗马数字包含以下七种字符: 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

1. 向左是减法，向右是加法
2. 构造一个数组，接收结果的值
3. 从左向右扫瞄字符串
4. 如果没有这种 IV 情况的存在，直接对应 map 值，加入数组即可
5. 现在只有一种特别情况：某些值在另一些值的左侧出现，则应该将这2个值做为一个整体来运算
   1. 2个一组的计算
   2. 1个一个的 mapping
6. 抽象：
   1. 循环字符串，结果数组，res= []
   2. 根据当前字符串，决定要不要传下一个字符串才能得到值
      1. 不需要传值，直接以 mapping 方式取值
      2. 需要传值，用 next值 - cur值，得到最终值，lengh--, arr.remove(next)
   3. sum(res);

问题分析思路2

1. 将所有字符，对应其值，生成一个 int 的数组
2. 将 int 中不合理的数据变得合理 (cur < next)，则交 cur 变成 - cur
3. 求和

问题分析思路3：

1. 将 IV/IX 等有出现右边减左边的情况做一个穷举
2. 然后 字符 串替换
3. 最后 sum

思路1

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/roman-to-integer
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

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

function ifeLeft(s) {
  if (s === "V" || s === "X") return "I";
  if (s === "L" || s === "C") return "X";
  if (s === "D" || s === "M") return "C";
}

function parse(rstring) {
  var parts = rstring.split("");
  var res = [];
  var len = parts.length;
  for (var i = 0; i < len; i++) {
    var cur = parts[i];
    var next = parts[i + 1];
    if (ifeLeft(next) === cur) {
      res.push(map[next] - map[ifeLeft(next)]);
      parts.splice(i + 1, 1);
      len--;
    } else {
      res.push(map[cur]);
    }
  }
  return res;
}

console.log(parse("III"));
console.log(parse("LVIII"));
console.log(parse("MCMXCIV"));

// 结果如下
[ 1, 1, 1 ]
[ 50, 5, 1, 1, 1 ]
[ 1000, 900, 90, 4 ]

思路2

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

function parse(str) {
  var parts = str.split("");
  var res = [];
  for (var i = 0; i < parts.length; i++) {
    const val = map[parts[i]];
    res.push(val);
  }
  return res;
}

function calc(list) {
  for (var i = 0; i < list.length - 1; i++) {
    var cur = list[i];
    var next = list[i + 1];
    if (cur < 0) continue;
    if (cur < next) {
      list[i] = cur * -1;
    }
  }
  return list;
}

function ro2int(str) {
  const list = calc(parse(str));
  return list.reduce((a, b) => a + b);
}

console.log(ro2int("III"));				// 5
console.log(ro2int("LVIII"));			// 58
console.log(ro2int("MCMXCIV"));			// 1994

思路3：

主要展示思路，性能可以继续远优化

/**
 * @param {string} s
 * @return {number}
 */
const items = [
  { code: "II", value: 2 },
  { code: "IV", value: 4 },
  { code: "IX", value: 9 },
  { code: "XL", value: 40 },
  { code: "XC", value: 90 },
  { code: "CD", value: 400 },
  { code: "CM", value: 900 },
  { code: "I", value: 1 },
  { code: "V", value: 5 },
  { code: "X", value: 10 },
  { code: "L", value: 50 },
  { code: "C", value: 100 },
  { code: "D", value: 500 },
  { code: "M", value: 1000 },
];

function romanToInt(str) {
  items.forEach((item) => (str = str.replace(new RegExp(item.code, "g"), item.value + ",")));
  const arr = eval(`[${str}]`);
  return arr.reduce((a, b) => a + b);
}

参考

• https://leetcode-cn.com/problems/roman-to-integer/