【LeetCode: 12. 整数转罗马数字 + 模拟 + 有序表】

发布时间:2024年01月22日

在这里插入图片描述

🚀 算法题 🚀

🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀
🌲 越难的东西,越要努力坚持,因为它具有很高的价值,算法就是这样?
🌲 作者简介:硕风和炜,CSDN-Java领域优质创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🌲 恭喜你发现一枚宝藏博主,赶快收入囊中吧🌻
🌲 人生如棋,我愿为卒,行动虽慢,可谁曾见我后退一步?🎯🎯

🚀 算法题 🚀

在这里插入图片描述
在这里插入图片描述

🚩 题目链接

? 题目描述

罗马数字包含以下七种字符: 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:

输入: num = 3
输出: “III”
示例 2:

输入: num = 4
输出: “IV”
示例 3:

输入: num = 9
输出: “IX”
示例 4:

输入: num = 58
输出: “LVIII”
解释: L = 50, V = 5, III = 3.
示例 5:

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

提示:

1 <= num <= 3999

🌟 求解思路&实现代码&运行结果


? 模拟 + 有序表

🥦 求解思路
  1. 该题和我们昨天求解的题目类似,只不过是相反的过程,还是要根据题目已经给好的关系进行映射,该题是数字映射罗马数字,然后模拟即可。
  2. 每次我们找到小于等于当前num的数cur(该过程可以通过有序表来加速),然后将其对应的value返回,进行拼接,然后num-=cur,继续重复这个过程,直到num等于0结束。
  3. 有了基本的思路,接下来我们就来通过代码来实现一下。
🥦 实现代码
class Solution {
    public String intToRoman(int num) {
        StringBuilder sb = new StringBuilder("");
        TreeMap<Integer, String> map = new TreeMap<>() {
            {
                put(1, "I");
                put(5, "V");
                put(4, "IV");
                put(10, "X");
                put(9, "IX");
                put(50, "L");
                put(40, "XL");
                put(100, "C");
                put(90, "XC");
                put(400, "CD");
                put(500, "D");
                put(900, "CM");
                put(1000, "M");
            }
        };
        while (num != 0) {
            Integer n = map.floorKey(num);
            String c = map.get(n);
            num -= n;
            sb.append(c);
        }
        return sb.toString();
    }
}
🥦 运行结果

在这里插入图片描述


💬 共勉

最后,我想和大家分享一句一直激励我的座右铭,希望可以与大家共勉!

在这里插入图片描述

在这里插入图片描述

文章来源:https://blog.csdn.net/Coder_ljw/article/details/135756923
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。