013 - 罗马数字转整数(roman-to-integer)

Create by jsliang on 2019-05-23 13:24:24
Recently revised in 2019-05-24 11:36:30

一 目录

不折腾的前端,和咸鱼有什么区别

目录
一 目录
二 前言
三 解题
3.1 解题 - for()
3.2 解题 - Map

二 前言

返回目录

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

三 解题

返回目录

  • 官方题解:无

解题千千万,官方独一家,上面是官方使用 * 进行的题解。

小伙伴可以先自己在本地尝试解题,再看看官方解题,最后再回来看看 jsliang 讲解下使用 JavaScript 的解题思路。

3.1 解法 - for()

返回目录

  • 解题代码
var romanToInt = function(s) {
  /**
   * 特殊情况
   * IV === 4
   * IX === 9
   * XL === 40
   * XC === 90
   * CD === 400
   * CM === 900
   * 正常情况
   * I === 1
   * V === 5
   * X === 10
   * L === 50
   * C === 100
   * D === 500
   * M === 1000
   */
  const arr = s.split('');
  let result = 0;

  for (let i = 0; i < arr.length; ) {
    if (arr[i] === 'I' && arr[i+1] === 'V') {
      result += 4;
      i = i + 2;
    } else if(arr[i] === 'I' && arr[i+1] === 'X') {
      result += 9;
      i = i + 2;
    } else if(arr[i] === 'X' && arr[i+1] === 'L') {
      result += 40;
      i = i + 2;
    } else if(arr[i] === 'X' && arr[i+1] === 'C') {
      result += 90;
      i = i + 2;
    } else if(arr[i] === 'C' && arr[i+1] === 'D') {
      result += 400
      i = i + 2;
    } else if(arr[i] === 'C' && arr[i+1] === 'M') {
      result += 900;
      i = i + 2;
    } else if (arr[i] === 'I') {
      result += 1;
      i = i + 1;
    } else if (arr[i] === 'V') {
      result += 5;
      i = i + 1;
    } else if (arr[i] === 'X') {
      result += 10;
      i = i + 1;
    } else if (arr[i] === 'L') {
      result += 50;
      i = i + 1;
    } else if (arr[i] === 'C') {
      result += 100;
      i = i + 1;
    } else if (arr[i] === 'D') {
      result += 500;
      i = i + 1;
    } else if (arr[i] === 'M') {
      result += 1000;
      i = i + 1;
    }
  }

  return result;
};
  • 执行测试

  • sMCMXCIV

  • return
1994
  • LeetCode Submit
✔ Accepted
  ✔ 3999/3999 cases passed (248 ms)
  ✔ Your runtime beats 88.79 % of javascript submissions
  ✔ Your memory usage beats 52.85 % of javascript submissions (40.2 MB)
  • 知识点

  • split()split() 方法使用指定的分隔符字符串将一个 String 对象分割成字符串数组,以将字符串分隔为子字符串,以确定每个拆分的位置。split() 详细介绍

  • 解题思路

图

通过 for() 来进行暴力破解是最快的。

就像有句话:“暴力一时爽,一直暴力一直爽 —— jsliang”。

首先,我们只需要将参数打成数组(或者不打成数组,在 JavaScript 中,String 也有 lengthstring[i])。

然后,通过 for() 暴力循环。如果是正常情况,那么 i+ 1,如果是特殊情况,那么需要跳过下一次循环,即 i = i + 2

最后,通过 result 的相加,即可以获取到最终结果。

3.2 解法 - Map

返回目录

  • 解题代码
var romanToInt = function(s) {
  /**
   * 特殊情况
   * IV === 4
   * IX === 9
   * XL === 40
   * XC === 90
   * CD === 400
   * CM === 900
   * 正常情况
   * I === 1
   * V === 5
   * X === 10
   * L === 50
   * C === 100
   * D === 500
   * M === 1000
   */
  let map = new Map();
  map.set('I', 1);
  map.set('V', 5);
  map.set('X', 10);
  map.set('L', 50);
  map.set('C', 100);
  map.set('D', 500);
  map.set('M', 1000)

  let result = 0;
  for (let i = 0; i < s.length; i++) {
    if (s[i] + s[i+1] === 'IV') {
      result += 4;
      i = i + 1;
    } else if(s[i] + s[i+1] === 'IX') {
      result += 9;
      i = i + 1;
    } else if(s[i] + s[i+1] === 'XL') {
      result += 40;
      i = i + 1;
    } else if(s[i] + s[i+1] === 'XC') {
      result += 90;
      i = i + 1;
    } else if(s[i] + s[i+1] === 'CD') {
      result += 400
      i = i + 1;
    } else if(s[i] + s[i+1] === 'CM') {
      result += 900;
      i = i + 1;
    } else {
      result += map.get(s[i]);
    }
  }

  return result;
};
  • 执行测试

  • sMCMXCIV

  • return
1994
  • LeetCode Submit
✔ Accepted
  ✔ 3999/3999 cases passed (208 ms)
  ✔ Your runtime beats 99.08 % of javascript submissions
  ✔ Your memory usage beats 6.84 % of javascript submissions (43.5 MB)
  • 知识点

  • Map:保存键值对。任何值(对象或者原始值) 都可以作为一个键或一个值。Map 详细介绍

  • 解题思路

图

个人感觉,该方法有点像脱裤子放屁 ——多此一举

首先,设置 Map,将正常情况存下来。

然后,遍历字符串,判断特殊情况,如果是特殊情况,需要跳过下一次循环,否则直接获取 Map 中对应的值。

最后,将结果通过 resultreturn 出去。


不折腾的前端,和咸鱼有什么区别!

图

jsliang 会每天更新一道 LeetCode 题解,从而帮助小伙伴们夯实原生 JS 基础,了解与学习算法与数据结构。

扫描上方二维码,关注 jsliang 的公众号,让我们一起折腾!

知识共享许可协议
jsliang 的文档库梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。

Copyright © jsliang.top 2019 all right reserved,powered by Gitbook该文件修订时间: 2019-06-14 17:46:32

results matching ""

    No results matching ""