经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » 编程经验 » 查看文章
【算法】LeetCode算法题-Roman To Integer
来源:cnblogs  作者:小川94  时间:2018/10/19 9:00:34  对本文有异议

这是悦乐书的第145次更新,第147篇原创

今天这道题和罗马数字有关,罗马数字也是可以表示整数的,如“I”表示数字1,“IV”表示数字4,下面这道题目就和罗马数字有关,你能猜到吗?

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第4题(顺位题号是17),给定一组罗马数字组成的字符串,将其转换为整数。

罗马数字包含下面7个字符:

符号 值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000

下面是些小例子,帮助我们更好理解组合规则。

输入: “III”
输出: 3

输入: “IV”
输出: 4

输入: “LVIII”
输出: 58
说明: L = 50,V = 5,III = 3。

输入: “MCMXCIV”
输出: 1994
说明: M = 1000,CM = 900,XC = 90,IV = 4。

本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。

02 分析题目

罗马数字通常从左到右从最大到最小排列,大数字在前做加法,小数字在前做减法。

V在I的前面就是V+I=5+1=6,X在I的前面就是X+I=10+1=11
L在X的前面就是L+X=50+10=60,C在X的前面就是C+X=100+10=110
D在C的前面就是D+C=500+100=600,M在C的前面就是M+C=1000+100=1100

I在V的前面就是V-I=5-1=4,I在X的前面就是X-I=10-1=9
X在L的前面就是L-X=50-10=40,X在C的前面就是C-X=100-10=90
C在D的前面就是D-C=500-100=400,C在M的前面就是M-C=1000-100=900

理解这些后,我们第一步是要将基础字符和所代表的数字存起来,这种类似键值对的组合,很容易让人联想到HashMap。

第二步就需要获取传入的字符串每个字符所代表的数字是什么,同时还要判断相邻两位字符所表示数字的大小关系,因为这决定着求总数的时候是做加法还是做减法。

第三步需要加上最后一位字符所表示的数字,因为相邻两位做比较,最后一次比较的是倒数第二位和倒数第一位,求和(差)只是算到了倒数第二位,所以在循环结束后,需要加上最后一位的值。因为最后一位字符后面再无其他字符,所以只能做加法。

  1. public static int romanToInt(String s) {
  2. int result = 0;
  3. Map<Character, Integer> map = new HashMap<Character, Integer>();
  4. map.put('I', 1);
  5. map.put('V', 5);
  6. map.put('X', 10);
  7. map.put('L', 50);
  8. map.put('C', 100);
  9. map.put('D', 500);
  10. map.put('M', 1000);
  11. if (s.length() == 0) {
  12. return 0;
  13. }
  14. char[] arr = s.toCharArray();
  15. int i=0, j=1;
  16. for (; i<arr.length-1; i++,j++) {
  17. if (map.get(arr[i]) >= map.get(arr[j])) {
  18. result += map.get(arr[i]);
  19. } else {
  20. result -= map.get(arr[i]);
  21. }
  22. }
  23. result += map.get(arr[i]);
  24. return result;
  25. }

03 小结

今天这道题还是比较简单的,弄清楚罗马数字的规则后,只需要将其演绎成相应代码即可。

如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!

本文首发于我的个人公众号:悦乐书,转载请注明出处!

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号