LeetCode小白菜笔记4:Roman to Integer

LeetCode小白菜笔记[4]:Roman to Integer13. Roman to Integer [Easy]

题目:Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

呃。。。这次题目很简单也很实用。而且发现需要恶补一下常识了…因为居然对罗马数字太不熟悉,只认识I,V,X 。因为很少见到较大数字的罗马数字表示,感觉日常一般都是用罗马数字作序数,因此也不会太大。而且对很多规则也不清楚。所以先补充一下关于罗马数字的常识:

Roman numerals (罗马数字)

罗马数字起源于古罗马并且直到晚期中世纪还是一种在欧洲流行的计数方法。罗马数字体系有7个拉丁字母作为元素,通过对其进行组合计数:

罗马帝国衰亡之后很长时间内,罗马数字仍然存在,直到从14世纪开始,才逐渐被阿拉伯数字取代。

基本的计数方法如下:

1-10之间的数字的最基本的表示方式(罗马数字是十进制的)

I, II, III, IV, V, VI, VII, VIII, IX, X

基本原则,在有两种符号的情况下,小数在左为减法(subtraction notation),小数在右为加法。注意,4和9的表示方法通常是以减法表示的。

然后10到100的表示为:

X, XX, XXX, XL, L, LX, LXX, LXXX, XC, C.

实际上就是用 X,L,C 分别替换了10以内时候的 I,V,X 。同理,100到1000为:

C, CC, CCC, CD, D, DC, DCC, DCCC, CM, M.

同时含有hundreds,tens,units的数字按照降序从左到右排列,和阿拉伯数字相同。但是不需要对缺失某一数量级的位数的位置占位。举几个栗子:(栗子来自wikipedia)

1776 as MDCCLXXVI, the date written on the book held by the Statue of Liberty.

1954 as MCMLIV, as in the trailer for the movie The Last Time I Saw Paris

1990 as MCMXC, used as the title of musical project Enigma’s debut album MCMXC a.D., named after the year of its release.

2014 as MMXIV, the year of the games of the XXII (22nd) Olympic Winter Games (in Sochi)

其他的规则如:左边减去的数字只能是I,X,C,不能是5,50,500之类;而且左键不可跨越位数,即只能相差一个量级,如 99 为XCIX(即 (100-10) + (10-1) ),而不能是IC(100 - 1)。跨越了位数。错误;另外,左减最多一个,右加最多三个。以及上方加线或者下标加M表示乘以1000。(突然明白为何这道题目限制输入范围,因为4000及以上需要用5000-1000来表示,无法应用上述规则啦)

基本规则就是以上,根据我们已知的规则,可以看出,在一个罗马数字中,大数一般是在高位,小数在低位,只有当小数为1,10,100并与后面的数字作减法的时候,才可以小数在大数前面。如:

MCMLIV = 1000 + (1000-100) + 50 + (5-1)

所以一种思路是:在字符串中检测右边比自己小的位置,将该位置的数加上负号,最后直接求和。(由于根据规则左减最多只有一位,所以只比较相邻两位即可)。另一种思路为,从高到低依次取数,如果下一个比现在大,就减去现在的数,否则就加上,最后一个肯定是加。emmm…….貌似这两种本质上也没啥区别。

当然,最先要建立一个码本将str存成list,每个元素都转成int。

代码如下:

灰常顺利的通过了。。。但是好像有点慢。

这个的结果:

稍稍好一些。

总结

如果能每一步直接计算且不需要返回中间变量的话就尽量直接计算,比如上述直接输出sum即可,不需要先转成带正负号的整数list。

python中的dict的key这里是字符串,要用 ‘ I ’ 而不是 I 。以及python里没有switch-case 语句 ,可能是因为有字典吧,可以实现类似的功能。

以及,平时要积累基本常识,免得到时候罗马数字都认不全「手动捂脸」。

THE END

星期一, 11. 十二月 2017 12:11上午

本文来自企鹅号 - 兔角与禅媒体

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

P2580 于是他错误的点名开始了

题目背景 XS中学化学竞赛组教练是一个酷爱炉石的人。 他会一边搓炉石一边点名以至于有一天他连续点到了某个同学两次,然后正好被路过的校长发现了然后就是一顿欧拉欧拉...

2717
来自专栏desperate633

Java Generic 自定义泛型如何自定义泛型自定义泛型的边界共变性,逆变性泛型对象的比较

考虑我们要实现了一个节点对象,这个对象可以自定义类型,我们可以用泛型语法进行如下的定义:

501
来自专栏从零开始学自动化测试

python笔记1-用python解决小学生数学题

前几天有人在群里给小编出了个数学题: 假设你有无限数量的邮票,面值分别为6角,7角,8角,请问你最大的不可支付邮资是多少元? 小编掰着手指头和脚趾头算了下,答案...

2779
来自专栏ml

向前字典排序

          next_permutation算法对区间元素进行一次组合排序,使之字典顺序大于原来的排序,有如下两个使用原形,对迭代器区间[first,l...

2489
来自专栏ml

HDUOJ---(2203)亲和串

亲和串 Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/...

3188
来自专栏前端架构

原码, 反码, 补码-减法变加法-同余理论:详解

一个数在计算机中的二进制表示形式,  叫做这个数的机器数。机器数是带符号的,在计算机用一个数的最高位存放符号, 正数为0, 负数为1.

591
来自专栏ml

HDUOJ---2152

Fruit Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Jav...

2596
来自专栏开发与安全

算法:堆栈与深度优先搜索(迷宫问题)

堆栈的访问规则被限制为Push和Pop两种操作,Push(入栈或压栈)向栈顶添加元素,Pop(出栈或弹出)则取出当前栈顶的元素,也就是说,只能访问栈顶元素而不能...

1929
来自专栏数据结构与算法

36:二进制分类

36:二进制分类 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 若将一个正整数化为二进制数,在此二进制数中,我们将数字1...

28210
来自专栏mukekeheart的iOS之旅

No.012 Integer to Roman

 12. Integer to Roman Total Accepted: 71315 Total Submissions: 176625 Difficulty...

2339

扫码关注云+社区