Leetcode打卡 | No.012 整数转罗马数字

写在前边:

欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!这个记录帖哪怕只有一个读者,小詹也会坚持刷下去的!


No.12 整数转罗马数字

原题:

罗马数字包含以下七种字符: 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: 输入: 3 输出: "III" #示例 2: 输入: 4 输出: "IV" #示例 3: 输入: 9 输出: "IX" #示例 4: 输入: 1994 输出: "MCMXCIV" 解释: M = 1000, CM = 900, XC = 90, IV = 4.

分析:最为简单粗暴的方法,可以使用面向过程的思路,比如给定一个数,逐次从高到低进行转换。一大堆的if~这个思路很容易看懂,这里小詹不做过多解释,看代码!

class Solution(object):
    def intToRoman(self, num):
        """
        :type num: int
        :rtype: str
        """
        result = ''
        #简单粗暴!从大到小依次处理,几个关键位置分别是:
        #1000;900;500;400;100;90;50;40;10;9;5;4;1
        while num > 0:
            if num >= 1000:
                result += 'M'
                num -= 1000
            elif num >= 900:
                result += 'CM'
                num -= 900
            elif num >= 500:
                result += 'D'
                num -= 500
            elif num >= 400:
                result += 'CD'
                num -= 400
            elif num >= 100:
                result += 'C'
                num -= 100
            elif num >= 90:
                result += 'XC'
                num -= 90
            elif num >= 50:
                result += 'L'
                num -= 50
            elif num >= 40:
                result += 'XL'
                num -= 40
            elif num >= 10:
                result += 'X'
                num -= 10
            elif num >= 9:
                result += 'IX'
                num -= 9
            elif num >= 5:
                result += 'V'
                num -= 5
            elif num >= 4:
                result += 'IV'
                num -= 4
            elif num >= 1:
                result += 'I'
                num -= 1
        return result

上边代码并不难懂,效果一般!这里已经注意到几个特殊的值,可以根据这些值做文章。下边提供一种网上的代码思路:通过构建字典和列表,从高位到低位依次进行转换输出。因为小詹把注释写的很详细,这里就不做赘述了!

原文发布于微信公众号 - 小詹学Python(xiaoxiaozhantongxue)

原文发表时间:2018-06-29

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ACM算法日常

2018南京大学计算机夏令营机试题

lipper同学问了我一个算法题,由于时间原因没来得及写,lipper同学就自己动手写了出来,并且顺手写了此篇博文,文笔潇洒,与君共勉。

2571
来自专栏猿人谷

oc 中随机数的用法(arc4random() 、random()、CCRANDOM_0_1()

1)、arc4random() 比较精确不需要生成随即种子        使用方法 :                  通过arc4random() 获取0到...

2248
来自专栏机器之心

教程 | 简单实用的pandas技巧:如何将内存占用降低90%

选自DATAQUEST 作者:Josh Devlin 机器之心编译 参与:Panda pandas 是一个 Python 软件库,可用于数据操作和分析。数据科学...

76910
来自专栏C/C++基础

基数排序简介及其并行化

  基数排序号称线性时间排序算法中性能最好,速度最快的排序算法。本文将简要概括其算法思想,串行代码及其并行化。

1201
来自专栏Petrichor的专栏

numpy库 简介

  NumPy 是一个 Python 包。 它代表 “Numeric Python”。 它是一个由多维数组对象和用于处理数组的例程集合组成的库。

1772
来自专栏Java Web

《编写高质量代码》学习笔记(1)

前言 看大神推荐的书单中入门有这么一本书,所以决定把这本书的精华(自认为很有用的点),或许是我自己现在能用到的点都提炼出来,供大家参考学习。 以下内容均出自《...

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

BZOJ3693: 圆桌会议(Hall定理 线段树)

我的思路:对于区间分两种情况讨论,一种是完全包含,另一种是部分包含。 第一种情况非常好判断,至于计算对于一个区间[l, r]的$\sum a[i]$就可以了,但...

1002
来自专栏desperate633

[编程题] 猜数游戏分析代码

首先我们分析,dp[i]表示前i个数的合法个数 当第i个数是素数的时候,前面除了1都没有能除尽的,所以这个位置可以随便选Y或N,所以dp[i] = dp[i-...

1083
来自专栏SimpleAI

Python高级特性——为什么都说Python高效

本微教程根据廖雪峰python教程中的部分内容,配合我个人的学习经历进行总结整理。

1084
来自专栏机器学习算法工程师

一道网易笔试题引发的血案……

作者:柳行刚 编辑:黄俊嘉 网易的2016年笔试题,题目经典。 所以特地找来给各位有兴趣的童鞋看看, 有详细的解题思路以及代码喔~ 各位,请看题! 题目描述: ...

44112

扫码关注云+社区