当前位置：首页 > 编程日记 > 正文

刻意练习：LeetCode实战 -- Task13. 罗马数字转整数

编程日记 2024-09-26 06:10:00

背景

本篇图文是LSGO软件技术团队组织的第二期基础算法（Leetcode）刻意练习训练营的打卡任务。本期训练营采用分类别练习的模式，即选择了五个知识点（数组、链表、字符串、树、贪心算法），每个知识点选择了三个简单、两个中等、一个困难等级的题目，共计三十道题，利用三十天的时间完成这组刻意练习。

本次任务的知识点：字符串

字符串或串（string） 是由数字、字母、下划线组成的一串字符。一般记为 s = “a1a2...an”（n >= 0）。它是编程语言中表示文本的数据类型。

通常以串的整体作为操作对象，如：在串中查找某个子串在该串中首次出现的位置、在串的某个位置上插入一个子串以及删除一个子串等。两个字符串相等的充要条件是：长度相等，并且各个对应位置上的字符都相等。串通常以顺序的方式进行存储与实现。

题目

题号：13
难度：简单
https://leetcode-cn.com/problems/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:

输入:"III"
输出: 3

示例 2:

输入: "IV"
输出: 4

示例 3:

输入: "IX"
输出: 9

示例 4:

输入: "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.

示例 5:

输入: "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

实现

第一种：直接法

根据“罗马数字中小的数字在大的数字的右边”以及六种特殊情况的规则直接去写代码。

执行结果：通过
执行用时：96 ms, 在所有 C# 提交中击败了 95.88% 的用户
内存消耗：25.7 MB, 在所有 C# 提交中击败了 5.27% 的用户

public class Solution
{public int RomanToInt(string s){int result = 0;int count = s.Length;int i = 0;while (i < count){char c = s[i];int move = 0;switch (c){case 'I':result += PreI(i, s, ref move);break;case 'V':result += 5;move = 1;break;case 'X':result += PreX(i, s, ref move);break;case 'L':result += 50;move = 1;break;case 'C':result += PreC(i, s, ref move);break;case 'D':result += 500;move = 1;break;case 'M':result += 1000;move = 1;break;}i += move;}return result;}private int PreI(int index, string s, ref int move){//I  1//IV 4//IX 9//II 2int result = 0;int count = s.Length;if (index + 1 < count){char c = s[index + 1];switch (c){case 'V':result = 4;move = 2;break;case 'X':result = 9;move = 2;break;case 'I':result = 2;move = 2;break;}}else{result = 1;move = 1;}return result;}private int PreX(int index, string s, ref int move){//X 10//XL 40//XC 90int result = 0;int count = s.Length;if (index + 1 < count){char c = s[index + 1];switch (c){case 'L':result = 40;move = 2;break;case 'C':result = 90;move = 2;break;default:result = 10;move = 1;break;}}else{result = 10;move = 1;}return result;}private int PreC(int index, string s, ref int move){//C 100//CD 400//CM 900int result = 0;int count = s.Length;if (index + 1 < count){char c = s[index + 1];switch (c){case 'D':result = 400;move = 2;break;case 'M':result = 900;move = 2;break;default:result = 100;move = 1;break;}}else{result = 100;move = 1;}return result;}
}

第二种：利用字典的方法

把罗马字符的所有组合作为key和value存到字典当中，每次取一个字符，判断这个字符之后是否还有字符。如果有，则判断这两个字符是否在字典中，如果存在则取值。否则，按照一个字符去取值即可。

执行结果：通过
执行用时：120 ms, 在所有 C# 提交中击败了 42.16% 的用户
内存消耗：25.8 MB, 在所有 C# 提交中击败了 5.27% 的用户

public class Solution
{public int RomanToInt(string s){Dictionary<string, int> dic = new Dictionary<string, int>();dic.Add("I", 1);dic.Add("II", 2);dic.Add("IV", 4);dic.Add("IX", 9);dic.Add("X", 10);dic.Add("XL", 40);dic.Add("XC", 90);dic.Add("C", 100);dic.Add("CD", 400);dic.Add("CM", 900);dic.Add("V", 5);dic.Add("L", 50);dic.Add("D", 500);dic.Add("M", 1000);int result = 0;int count = s.Length;int i = 0;while (i < count){char c = s[i];if (i + 1 < count && dic.ContainsKey(s.Substring(i, 2))){result += dic[s.Substring(i, 2)];i += 2;}else{result += dic[c.ToString()];i += 1;}}return result;}
}

Python 语言

执行结果：通过
执行用时：72 ms, 在所有 Python3 提交中击败了 24.93% 的用户
内存消耗：13.5 MB, 在所有 Python3 提交中击败了 5.05% 的用户

class Solution:def romanToInt(self, s: str) -> int:dic = {"I": 1, "II": 2, "IV": 4, "IX": 9, "X": 10, "XL": 40, "XC": 90,"C": 100, "CD": 400, "CM": 900, "V": 5,"L": 50, "D": 500, "M": 1000}result = 0count = len(s)i = 0while i < count:c = s[i]if i + 1 < count and s[i:i + 2] in dic:result += dic[s[i:i + 2]]i += 2else:result += dic[c]i += 1return result

往期活动

LSGO软件技术团队会定期开展提升编程技能的刻意练习活动，希望大家能够参与进来一起刻意练习，一起学习进步！

Python基础刻意练习活动即将开启，你参加吗？
Task01：变量、运算符与数据类型
Task02：条件与循环
Task03：列表与元组
Task04：字符串与序列
Task05：函数与Lambda表达式
Task06：字典与集合
Task07：文件与文件系统
Task08：异常处理
Task09：else 与 with 语句
Task10：类与对象
Task11：魔法方法
Task12：模块

我是终身学习者“老马”，一个长期践行“结伴式学习”理念的 中年大叔。

我崇尚分享，渴望成长，于2010年创立了“LSGO软件技术团队”，并加入了国内著名的开源组织“Datawhale”，也是“Dre@mtech”、“智能机器人研究中心”和“大数据与哲学社会科学实验室”的一员。

愿我们一起学习，一起进步，相互陪伴，共同成长。

后台回复「搜搜搜」，随机获取电子资源！
欢迎关注，请扫描二维码：

https://www.dkcj.cn/info/20377.html

刻意练习：LeetCode实战 -- Task13. 罗马数字转整数

背景

题目

实现

相关文章：

[翻译]ASP.NET MVC 3 开发的20个秘诀（十二）[20 Recipes for Programming MVC 3]：缩放图片尺寸创建缩略图...

Vue.js双向绑定的实现原理

学习UI设计的一些小技巧你会了吗

30个精美的模板，贺卡，图形圣诞素材

刻意练习：LeetCode实战 -- Task14. 最长公共前缀

6.1.1 验证注解的使用

Javascript创建数组的方式你了解了吗

loadrunner另类玩法【测试帮日记公开课】

刻意练习：LeetCode实战 -- Task15. 有效的括号

对口令协议的几种攻击方式

初学者如何学Java开发

[算法] [常微分方程] [欧拉法改进欧拉法经典R-K算法]

刻意练习：LeetCode实战 -- Task16. 无重复字符的最长子串

轻松实现QQ用户接入

web前端培训之Javascript如何改变数组的长度?

刻意练习：LeetCode实战 -- Task17. 最长回文子串

CvBlobTrackerCC 多目标跟踪算法简析

linux基础学习（二）

ui设计培训需要什么基础?如何入门学习?

SQL Server日志清除的两种方法 .

刻意练习：LeetCode实战 -- Task18. 正则表达式匹配

CentOS7启动图形界面

Java培训学习步骤有哪些

extjs 4 tab panel得strip在IE下右偏解决办法

Vbox共享文件夹不显示了

刻意练习：LeetCode实战 -- Task19. 相同的树

找Java培训机构需要注意那些

字符串的最大相似匹配

刻意练习：LeetCode实战 -- Task20. 对称二叉树

洛谷 P1598 垂直柱状图【字符串+模拟】