Emove

  • 首页
  • 归档
  • 分类
  • 标签

  • 搜索
context 反射 channel LRU BeanDefinition JVM 装饰者模式 MyBatis 快慢指针 归并排序 链表 hash表 栈 回溯 贪心 主从复制 二分查找 双指针 动态规划 AOF RDB 规范 BASE理论 CAP B树 RocketMQ Sentinel Ribbon Eureka 命令模式 访问者模式 迭代器模式 中介者模式 备忘录模式 解释器模式 状态模式 策略模式 职责链模式 模板方法模式 代理模式 享元模式 桥接模式 外观模式 组合模式 适配器模式 建造者模式 原型模式 工场模式 单例 UML 锁 事务 sql 索引

整数转罗马数字

发表于 2020-04-12 | 分类于 算法题 | 0 | 阅读次数 155

题目:整数转罗马数字

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

int2roman

例如, 罗马数字 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 到 3999 的范围内。

例如:
输入:3	 4	  9		58		1994
输出:"III" "IV"  "IX"  "LVIII"  "MCMXCIV"

题解:

  1. 把罗马数字和对应的数值维护成表或者数组
  2. 贪心算法,每次去计算当前的num可以取的最大的罗马数字

题解代码如下:

class Solution {
    public String intToRoman(int num) {
        StringBuilder roman = new StringBuilder();
        String[] romans = {"I", "IV", "V", "IX", "X", "XL", "L", "XC", "C", "CD", "D", "CM", "M"};
        int[] convert = {1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000};
        int index = convert.length - 1;
        while (num > 0) {
            for (int i = index; i >= 0; i--) {
                int temp = convert[i];
                if (num >= temp) {
                    num = num - temp;
                    roman.append(romans[i]);
                    index = i;
                    break;
                }
            }
        }
        return roman.toString();
    }
}
# context # 反射 # channel # LRU # BeanDefinition # JVM # 装饰者模式 # MyBatis # 快慢指针 # 归并排序 # 链表 # hash表 # 栈 # 回溯 # 贪心 # 主从复制 # 二分查找 # 双指针 # 动态规划 # AOF # RDB # 规范 # BASE理论 # CAP # B树 # RocketMQ # Sentinel # Ribbon # Eureka # 命令模式 # 访问者模式 # 迭代器模式 # 中介者模式 # 备忘录模式 # 解释器模式 # 状态模式 # 策略模式 # 职责链模式 # 模板方法模式 # 代理模式 # 享元模式 # 桥接模式 # 外观模式 # 组合模式 # 适配器模式 # 建造者模式 # 原型模式 # 工场模式 # 单例 # UML # 锁 # 事务 # sql # 索引
盛最多水的容器
Redis主从复制关于应用中的问题
  • 文章目录
  •   |  
  • 概览
林亦庭

林亦庭

less can be more

87 文章
11 分类
54 标签
RSS
Github
Creative Commons
© 2021 林亦庭
粤ICP备20029050号