算法-罗马数字转整数,罗马数字、天平、算盘之间的关系

645 阅读4分钟

关键词 罗马数字 罗马数字转十进制 算盘和算法

这道题在leetcode的题库中不算难, 但怎么能更快的讲清楚这道题的解题思路还是有点难度的!

一直想给罗马数字找一个更形象的说明, 今天发现两样东西和罗马数字的工作原理非常像。1.算盘;2.天平。

1.leetcode 原题

罗马数字的历史很有趣,百科上有介绍。关于本题认真审题就可以作答了。

重点信息1

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

如果拿天平的砝码来和罗马数字全部的字符比较是不是很像,而天平又是怎么工作的呢?

天平是通过加和所有右侧托盘的砝码重量和游标卡尺上的刻度重量来计算最终结果的。

重点信息2

这个特殊的规则只适用于以下六种情况:

  • I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。
  • X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。
  • C 可以放在 D (500) 和 M (1000) 的左边,来表示 400 和 900。

这是不是告诉我们还有其他重量的砝码存在呢?

字符 数值 砝码
IV 4 4克
. . .
CM 900 900克

显然这部分就没法用砝码来标示了,卡尺也无法在这么多段程中起到作用。如果有n多盒可用的砝码来用,那么可能就乱套了!罗马数字里并没有用“IIIV”来表示2的, 除非有“二神”。例如: 我家座钟的表盘用“IIII”来表示4(因为IV和神朱比特重名了)。

随便找了个罗马数字表盘图

重点信息3

这里是用来补充信息2的,用算盘来标识罗马数字就必须留出中间的档(一根一根穿过梁的细杆子,叫做“档”)给这些特殊情况用。

只用下面的算珠来表示就可以了。

2. 实现

通过一通分析,可以得出这样几个重点:

  1. 要有“砝码”,标准的符号,建一个map
  2. 要解决特殊规则的问题,根据描述做一个逻辑判断来解决
  3. 最后的结果一定是家和在一起的

理解了重点,代码也就好写了。

代码如下:

var romanToInt = function(s) {
    const romanObj = {
        I: 1,
        V: 5,
        X: 10,
        L: 50,
        C: 100,
        D: 500,
        M: 1000
      };
      // 知识点 reduce 是一个比较重要的函数
      const res = s.split('').reduce((sum, current, index, arr) => {
        sum = sum + romanObj[current];
        /* 假设输入IV,第一次遍历到I 
        * sum为1,第二次遍历sum为6。但是返回要求是4,所以这里存在的普遍规律就可以这样处理
        * 5-1(IV本身所代表的)再减掉1(I加上来的),同理其他情况也是一样
        */
        if ((current === 'V' || current === 'X') && arr[index - 1] === 'I') sum -= 2;
        if ((current === 'L' || current === 'C') && arr[index - 1] === 'X') sum -= 20;
        if ((current === 'D' || current === 'M') && arr[index - 1] === 'C') sum -= 200;
        return sum;
      }, 0);
      return res;
};

无关这道题难易程度,这种思路估计我很长一段时间忘不掉了! reduce知识点

3. 知行合一实践

本文算是对知行合一的一个小实践 - 沉浸式体验。

下面是大成至圣先师向音乐老师的学习过程,里面充分的体现了圣人的学习境界-琢磨、揣摩、着魔的三种境界。

孔子学鼓琴师襄子,十日不进。
师襄子曰:“可以益矣。”孔子曰:“丘已习其曲矣,未得其数也。”
有间,曰:“已习其数可以益矣。”孔子曰:“丘未得其志也。”
有间,曰:“已习其志,可以益矣。”孔子曰:“丘未得其为人也。”
有间,曰:“有所穆然深思焉,有所怡然高望而远志焉。”
曰:“丘得其为人,黯然而黑,几然而长,眼如望羊,
如王四国,非文王其谁能为此也!”师襄子辟席再拜,
曰:“师盖云《文王操》也。”
——《史记·孔子世家》