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 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

洛谷P4779 【模板】单源最短路径(标准版)

前几天写dijkstra的时候没打vis标记居然A了,然后天真的我就以为Dijkstra不用打标记。

1053
来自专栏JAVA高级架构

程序员必须掌握的600个英语单词

762
来自专栏专知

关关的刷题日记94 – Leetcode 153. Find Minimum in Rotated Sorted Array

点击上方“专知”,关注获取专业AI知识” 关关的刷题日记94 – Leetcode 153. Find Minimum in Rotated Sorted Ar...

33310
来自专栏陈满iOS

iOS图形处理概论:OpenGL ES,Metal,Core Graphics,Core Image,GPUImage,Scene Kit (3D) ,Sprite Kit (2D),OpenCV

对于刚接触iOS图形相关框架的小白,有一些图形框架在字面上和功能上非常容易混淆。这里旨在总结一下各种框架,区分它们的概念和功能,以作日后进一步细分学习的指引。因...

1202
来自专栏海天一树

2017年第二十三届NOIP(C语言)普及组初赛试题及详细答案

竞赛时间: 2017 年 10月14日 14:30~ 16:30 选手注意:不得使用任何电子设备(如计算器、手机、电子词典等 )或查阅任何书籍资料

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

1026 逃跑的拉尔夫

1026 逃跑的拉尔夫 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 年轻的...

3538
来自专栏前端笔记

【 图形游戏 Tetris 】原生 JavaScript 做小游戏

俄罗斯方块 (俄罗斯开发经典游戏) 游戏简介 《俄罗斯方块》(Tetris, 俄文:Тетрис)是一款由俄罗斯人阿列克谢·帕基特诺夫于1984年6月发明的休闲...

32110
来自专栏LET

斐波那契数列之美

1947
来自专栏大数据文摘

如何利用维基百科的数据可视化当代音乐史

1747
来自专栏GIS讲堂

OpenLayers3基础教程——OL3基本概念

从本节开始,我会陆陆续续的更新有关OL3的相关文章——OpenLayers3基础教程,欢迎大家关注我的博客,同时也希望我的博客能够给大家带来一点帮助。

1183

扫码关注云+社区