写点什么

【LeetCode】整数转罗马数字 Java 题解

用户头像
HQ数字卡
关注
发布于: 2021 年 05 月 14 日

题目描述

罗马数字包含以下七种字符: I, V, X, L,C,D 和 M。


字符          数值I             1V             5X             10L             50C             100D             500M             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:
输入: num = 3输出: "III"
来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/integer-to-roman著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码

思路分析

  • 这个题目题意容易理解,按照要求写代码就可以完成题目。

  • 之前没有做过这个题目,初步使用暴力法,可以 AC 但是代码太冗余。暴力法很重要,间接帮助发现了冗余的部分,从而找到优化的空间。

  • 采用缓存的思想,优化代码结构,增强代码的可读性。

AC 代码

暴力法


public String intToRoman(int num) { StringBuilder ans = new StringBuilder();
if (num / 1000 > 0) { ans.append(getNumberRoman(num / 1000)); num %= 1000; } if (num / 100 > 0) { ans.append(getNumberRoman1(num / 100)); num %= 100; } if (num / 10 > 0) { ans.append(getNumberRoman2(num / 10)); num %= 10; } if (num > 0 ) { ans.append(getNumberRoman3(num)); }
return ans.toString(); }
public String getNumberRoman(int num) { String ans = ""; switch (num) { case 1: ans = "M"; break; case 2: ans = "MM"; break; case 3: ans = "MMM"; break; default: break; }
return ans; }
public String getNumberRoman1(int num) { String ans = ""; switch (num) { case 1: ans = "C"; break; case 2: ans = "CC"; break; case 3: ans = "CCC"; break; case 4: ans = "CD"; break; case 5: ans = "D"; break; case 6: ans = "DC"; break; case 7: ans = "DCC"; break; case 8: ans = "DCCC"; break; case 9: ans = "CM"; break; default: break; }
return ans; }

public String getNumberRoman2(int num) { String ans = ""; switch (num) { case 1: ans = "X"; break; case 2: ans = "XX"; break; case 3: ans = "XXX"; break; case 4: ans = "XL"; break; case 5: ans = "L"; break; case 6: ans = "LX"; break; case 7: ans = "LXX"; break; case 8: ans = "LXXX"; break; case 9: ans = "XC"; break; default: break; }
return ans; }

public String getNumberRoman3(int num) { String ans = ""; switch (num) { case 1: ans = "I"; break; case 2: ans = "II"; break; case 3: ans = "III"; break; case 4: ans = "IV"; break; case 5: ans = "V"; break; case 6: ans = "VI"; break; case 7: ans = "VII"; break; case 8: ans = "VIII"; break; case 9: ans = "IX"; break; default: break; }
return ans; }
复制代码

缓存优化

    public String intToRoman(int num) {        int[] nums = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};        String[] romans = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
StringBuilder ans = new StringBuilder();
int idx = 0; while (idx < 13) { while (num >= nums[idx]) { ans.append(romans[idx]); num -= nums[idx]; } idx++; }
return ans.toString(); }
复制代码

总结

  • 暴力法的时间复杂度是 O(n), 空间复杂度是 O(1)

  • 优化方法的时间复杂度是 O(n), 空间复杂度是 O(1)

  • 虽然两者的时间复杂度相同,但是采用缓存优化的方法执行效果更好!

  • 坚持每日一题,加油!

发布于: 2021 年 05 月 14 日阅读数: 11
用户头像

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

评论

发布
暂无评论
【LeetCode】整数转罗马数字Java题解