【打卡算法】13、罗马数字转整数算法解析

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群&＃xff1a;1040082875

大家好&＃xff0c;我是小魔龙&＃xff0c;Unity3D软件工程师&＃xff0c;VR、AR&＃xff0c;虚拟仿真方向&＃xff0c;不定时更新软件开发技巧&＃xff0c;生活感悟&＃xff0c;觉得有用记得一键三连哦。

一、题目

1、算法题目

“将输入的罗马数字转化成整数。”

题目链接&＃xff1a;
来源&＃xff1a;力扣&＃xff08;LeetCode&＃xff09;

链接&＃xff1a;13. 罗马数字转整数 - 力扣&＃xff08;LeetCode&＃xff09; (leetcode-cn.com)

2、题目描述

罗马数字包含以下七种字符&＃xff1a; I&＃xff0c; V&＃xff0c; X&＃xff0c; L&＃xff0c;C&＃xff0c;D 和 M。

例如&＃xff0c; 罗马数字 2 写做 II &＃xff0c;即为两个并列的 1。12 写做 XII &＃xff0c;即为 X &＃43; II 。 27 写做 XXVII, 即为 XX &＃43; V &＃43; II 。

通常情况下&＃xff0c;罗马数字中小的数字在大的数字的右边。但也存在特例&＃xff0c;例如 4 不写做 IIII&＃xff0c;而是 IV。数字 1 在数字 5 的左边&＃xff0c;所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地&＃xff0c;数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况&＃xff1a;

I 可以放在 V (5) 和 X (10) 的左边&＃xff0c;来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边&＃xff0c;来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边&＃xff0c;来表示 400 和 900。

给你一个罗马数字&＃xff0c;将其转为整数。输入确保在 1 到 3999 的范围内。

示例 1&＃xff1a;
输入&＃xff1a;num &＃61; "III"
输出&＃xff1a;3


示例 2&＃xff1a;
输入&＃xff1a;num &＃61; "XLVIII"
输出&＃xff1a;48
解析: XL &＃61; 40 , V &＃61; 5 , III &＃61; 3


示例 3&＃xff1a;
输入&＃xff1a;num &＃61; "MIVCMXCIV"
输出&＃xff1a;4994
解析&＃xff1a;MIV &＃61; 4000 , CM &＃61; 900 , XC &＃61; 90 , IV &＃61; 4


二、解题

1、思路分析

罗马数字转整数&＃xff0c;主要分两种情况&＃xff1a;

• 一种是大数字在前&＃xff0c;小数字在后&＃xff0c;这种就可以将每个字符转化成一个值&＃xff0c;累加即可。比如VI&＃61;5&＃43;1&＃61;6
• 一种是小数字在大数字前的情况&＃xff0c;需要根据规则减去小的数字&＃xff0c;这种就可以将每个字符转化成一个值&＃xff0c;若数字右侧的数字比自身大&＃xff0c;就将该数字符号取反。比如 XIV &＃61; X - I &＃43; V &＃61;10 - 1 &＃43; 5 &＃61; 14

2、代码实现

模拟法&＃xff1a;

根据解题思路&＃xff0c;将输入的罗马数字依次比较&＃xff0c;分成两种情况进行计算&＃xff1a;

public class Solution
{public int RomanToInt(string s) {Dictionary<char, int> Values &＃61; new Dictionary<char, int> { { &＃39;I&＃39;, 1 }, { &＃39;V&＃39;, 5 }, { &＃39;X&＃39;, 10 }, { &＃39;L&＃39;, 50 }, { &＃39;C&＃39;, 100 }, { &＃39;D&＃39;, 500 }, { &＃39;M&＃39;, 1000 } };int ans &＃61; 0;int n &＃61; s.Length;for (int i &＃61; 0; i < n; &＃43;&＃43;i){int value &＃61; Values[s[i]];if (i < n - 1 && value < Values[s[i &＃43; 1]]){ans -&＃61; value;}else{ans &＃43;&＃61; value;}}return ans;}
}


替换字符串

这是一种比较有趣的解法&＃xff0c;利用C#的字符串替换的方法&＃xff0c;将两个特殊字符替换成一个字符&＃xff0c;然后字符转化成对应的唯一数字&＃xff0c;进行加法即可。

public class Solution
{public int RomanToInt(string s) {s &＃61; s.Replace("IV","Y");s &＃61; s.Replace("IX","T");s &＃61; s.Replace("XL","U");s &＃61; s.Replace("XC","R");s &＃61; s.Replace("CD","O");s &＃61; s.Replace("CM","W");int sum &＃61; 0;int i &＃61; 0;for (i &＃61; 0; i < s.Length; i&＃43;&＃43;){switch (s[i]){case &＃39;M&＃39;:sum &＃43;&＃61; 1000;break;case &＃39;W&＃39;:sum &＃43;&＃61; 900;break;case &＃39;D&＃39;:sum &＃43;&＃61; 500;break;case &＃39;O&＃39;:sum &＃43;&＃61; 400;break; case &＃39;C&＃39;:sum &＃43;&＃61; 100;break;case &＃39;R&＃39;:sum &＃43;&＃61; 90;break;case &＃39;L&＃39;:sum &＃43;&＃61; 50;break;case &＃39;U&＃39;:sum &＃43;&＃61; 40;break;case &＃39;X&＃39;:sum &＃43;&＃61; 10;break;case &＃39;T&＃39;:sum &＃43;&＃61; 9;break;case &＃39;V&＃39;:sum &＃43;&＃61; 5;break;case &＃39;Y&＃39;:sum &＃43;&＃61; 4;break;case &＃39;I&＃39;:sum &＃43;&＃61; 1;break;}}return sum;}
}


3、时间复杂度

时间复杂度 &＃xff1a; O(n)

其中 n 是字符串 s 的长度。

空间复杂度&＃xff1a; O(1)

计算量与输入数字的大小无关。

三、总结

这道题识构建一个字典记录所有罗马数字子串&＃xff0c;然后根据大数字在前还是小数字在前分成两种情况&＃xff0c;然后不同情况不同分析。

在解题的时候&＃xff0c;就需要将所有的情况考虑到&＃xff0c;不然的话转化的结果就会有些出入。