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

关注

发布于: 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

原文链接:【http://xie.infoq.cn/article/bc14154313318c7c6c4c6586b】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

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

题目描述

思路分析

AC 代码

暴力法

缓存优化

总结

HQ数字卡

评论