让我们一起啃算法----罗马数字转整数

栏目: IT技术 · 发布时间: 4年前

内容简介:题干:罗马数字包含以下七种字符: I, V, X, L,C,D 和 M。字符    数值

罗马数字转整数(Roman-To-Integer)

题干:

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

输入: "LVIII"

输出: 58

解释: L = 50, V= 5, III = 3.

示例 2:

输入: "MCMXCIV"

输出: 1994

解释: M = 1000, CM = 900, XC = 90, IV = 4.

来源:力扣

题目有点长,耐心读一下哦,整体来说是比较简单的。

解题思路

根据题意我们可以知道单个罗马字母和数字的映射关系,例如 V 表示 数字 5 ,只是这里有一个问题: 罗马字母的组合形式对应的数字并不是单个罗马字母对应的数字之和 。 例如 CD 对应的数字是 400 ,而单个 C 对应的数字为 100 ,单个 D 对应的数字为 500

根据规律可以发现(当然题干也明确说明了),当罗马数字中小数在大数左边时,所表示的数等于大数减去小数的值。 例如 CD 对应的数字是 单个 D 对应的数值减去单个 C 对应的数值,即 500 - 100 = 400 。所以我们只需要遍历目标字符串,判断当前的罗马字符对应的数值 cur 与下一个罗马字符对应的数值 next 的大小, cur 小于 next减去 cur 的值 ,反之则 加上 cur 的值

流程图如下:

让我们一起啃算法----罗马数字转整数

代码实现

// 罗马数字转成整数
func getIntByRoman(r byte) int {
    switch r {
    case 'I':
        return 1
    case 'V':
        return 5
    case 'X':
        return 10
    case 'L':
        return 50
    case 'C':
        return 100
    case 'D':
        return 500
    case 'M':
        return 1000
    default:
        return 0
    }
}

func romanToInt(s string) int {
    res := 0
    i := 0
    // 跳出循环之后,i刚好指向字符串s的最后一个字符
    for ; i < len(s)-1; i ++ {
        cur := getIntByRoman(s[i])
        next := getIntByRoman(s[i+1])
        // 比较值,如果当前值比下一个值小则减去当前值,反之则加上当前值
        if cur < next {
            res -= cur
        } else {
            res += cur
        }
    }
    // 注意最后一个值需要加上
    res += getIntByRoman(s[i])
    return res
}

总结

每天进步一点点,加油!

算法教程项目,每天更新一题,点个 star 支持一下呀:

https://github.com/wx-satellite/learning-a...

欢迎关注我们的微信公众号,每天学习 Go 知识

让我们一起啃算法----罗马数字转整数

以上所述就是小编给大家介绍的《让我们一起啃算法----罗马数字转整数》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

高效程序员的45个习惯

高效程序员的45个习惯

Venkat Subramaniam、Andy Hunt / 钱安川、郑柯 / 人民邮电出版社 / 2010-01 / 35.00元

“书中‘切身感受’的内容非常有价值——通过它我们可以做到学有所思,思有所悟,悟有所行。” ——Nathaniel T. Schutta,《Ajax基础教程》作者 “此书通过常理和经验,阐述了为什么你应该在项目中使用敏捷方法。最难得的是,这些行之有效的实战经验,竟然从一本书中得到了。” ——Matthew Johnson,软件工程师 十年来,软件行业发生了翻天覆地的变化。敏捷......一起来看看 《高效程序员的45个习惯》 这本书的介绍吧!

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具