【算法攻坚】整数转罗马数字

简介: 【算法攻坚】整数转罗马数字

今日题目1


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


思路


罗马数字的组合个数是有限的,所以可以通过把有限的状态存储起来,然后把数字拆解成基本的罗马数字状态,把罗马数字的组合类比成阿拉伯数字的位(个十百千....),

然后通过把数字依次递减的用最大“位"来凑出这个输入的数字


同时,要保证存储的状态是从大到小排列的,这样就可以方便的吧数字优先通过最大的罗马数字组合而成


此时就想到了Java中的LinkedHashMap来实现


整体的思想用的是贪心思想,总是想从最大的开始,类似的题目还有找零钱。其实整体难度不算太大,如果能找到组合规律,应该很快就能写出来,


在手写的时候遇到个小问题,在用惯了IDEA写代码后,发现手写map的循环还是有难度的,因为会设计map的内部类entry,需要多练习几遍


public String intToRoman(int num) {
    //结果
    StringBuilder result = new StringBuilder();
    //构造状态
    Map<Integer, String> int2roman = initData();
    Set<Map.Entry<Integer,String>> entrys = int2roman.entrySet();
    for(Map.Entry<Integer, String> entry: entrys){
        while(num >= entry.getKey()){
            //也可以用除法的方案
            num = num -entry.getKey();
            result.append(entry.getValue());
        }
    }
    return result.toString();
}
private  Map<Integer, String> initData(){
    //必须保证有序,可以用两个数组、链表、LinkedHashMap等保证有序
    Map<Integer, String> int2roman = new LinkedHashMap<>();
    int2roman.put(1000, "M");
    int2roman.put(900, "CM");
    int2roman.put(500, "D");
    int2roman.put(400, "CD");
    int2roman.put(100, "C");
    int2roman.put(90, "XC");
    int2roman.put(50, "L");
    int2roman.put(40, "XL");
    int2roman.put(10, "X");
    int2roman.put(9, "IX");
    int2roman.put(5, "V");
    int2roman.put(4, "IV");
    int2roman.put(1, "I");
    return int2roman;
}


执行用时:6 ms, 在所有 Java 提交中击败了30.10%的用户

内存消耗:37.9 MB, 在所有 Java 提交中击败了47.39%的用户


解法二


还有一种暴力解法,主要是利用了输入1 <= num <= 3999,在一定的范围内,所以直接把不同的位数组合起来,这种解法我觉没啥必要学习,也不够通用,这里就不在列举了,有兴趣的可以再自己写写试试。


小结


贪心算法是解决寻找全局最优解时先确定局部最优解,然后把局部最优解不断迭代,从而获得整体最优解,

这样题目也有很多,在遇到几个类似的时候,我们再尝试总结下它们的特性和解题方法。


今天多学一点,明天就少说一句求人的话,加油!


目录
相关文章
|
6月前
|
算法 Java
[Java·算法·简单] LeetCode 13. 罗马数字转整数 详细解读
[Java·算法·简单] LeetCode 13. 罗马数字转整数 详细解读
60 0
|
3月前
|
人工智能 算法
第一周算法设计与分析:C : 200和整数对之间的情缘
这篇文章介绍了解决算法问题"200和整数对之间的情缘"的方法,通过统计数组中每个数模200的余数,并计算每个同余类中数的组合数来找出所有满足条件的整数对(i, j),使得\( A_i - A_j \)是200的整数倍。
|
4月前
|
算法
【算法】二分查找(整数二分和浮点数二分)
算法学习——二分查找(整数二分和浮点数二分)
41 0
【算法】二分查找(整数二分和浮点数二分)
|
6月前
|
算法 C语言
【C语言】求最小新整数(贪心算法)
【C语言】求最小新整数(贪心算法)
67 1
|
5月前
|
SQL 算法 数据挖掘
深入探索力扣第12题:整数转罗马数字的算法之旅
深入探索力扣第12题:整数转罗马数字的算法之旅
|
6月前
|
算法
简记二分算法模板与代码案例:整数二分和浮点数二分
本文介绍了两种算法模板,分别是整数二分和浮点数二分。
47 0
|
6月前
|
算法 测试技术 C++
【数论】【分类讨论】【C++算法】1611使整数变为 0 的最少操作次数
【数论】【分类讨论】【C++算法】1611使整数变为 0 的最少操作次数
|
6月前
|
算法 测试技术 C++
【数位dp】【C++算法】600. 不含连续1的非负整数
【数位dp】【C++算法】600. 不含连续1的非负整数
|
6月前
|
算法
算法题 — 整数转二进制,查找其中1的数量
算法题 — 整数转二进制,查找其中1的数量
43 0
|
15天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。