题目描述

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

题目分析

• 罗马字符和数值对应
• 小的数通常在大的数右边
• 存在六种特例

参数说明

/**
 * @param {string} s
 * @return {number}
 */

题解及实现

• 总体思路
  因为只有相邻的两个数之间才能构成六种特例中的一种,从索引为 0 开始,对比两个相邻的数,若满足索引 i 的数大于索引 i+1 的数,则说明索引为 i 的数不参与特例的构成,加之,若小于,则说明参与了特例的构成,对比特例和通常关系可以发现,对于构成特例的两个数,对左边的数做减操作,右边的数做加操作,右边的数与不构成特例的单个数操作相同,故只需对左边的数做减操作即可,无论是否构成特例,都右移一位遍历

1. hashMap

用 hashMap 存储字符和数值的对应关系

var romanToInt = function (s) {
  let hashMap = {
    I: 1,
    V: 5,
    X: 10,
    L: 50,
    C: 100,
    D: 500,
    M: 1000,
  };
  let i = -1;
  let sum = 0;
  while (++i < s.length - 1) {
    sum += hashMap[s[i]] >= hashMap[s[i + 1]] ? hashMap[s[i]] : -hashMap[s[i]];
  }
  sum += hashMap[s[i]];
  return sum;
};

时间复杂度:O(n),输入字符串长度

• 资源使用情况
  • 执行用时：172 ms, 在所有 JavaScript 提交中击败了 74.19%的用户
  • 内存消耗：42.9 MB, 在所有 JavaScript 提交中击败了 46.26%的用户
    问题:使用hashMap对空间占用高

2. switch

把映射放在switch中

var romanToInt = function (s) {
    let i = -1;
    let sum =  getVal(s[s.length-1]);
    while (++i < s.length - 1) {
        sum += getVal(s[i]) >= getVal(s[i + 1]) ? getVal(s[i]) : -getVal(s[i]);
    }
    return sum;
};
function getVal(ch) {
    switch (ch) {
        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;
    }
}

• 资源使用情况
  • 执行用时：144 ms, 在所有 JavaScript 提交中击败了 100.00%的用户
  • 内存消耗：42.5 MB, 在所有 JavaScript 提交中击败了 66.26%的用户
    问题:增加一个函数

github:每日算法同步更新