萤火小屋

优律的知识库

  • 首页
  • 归档
  • 分类
  • 标签
  • 留言
  • 关于

  • 搜索
消息队列 RabbitMQ Redis 双指针 力扣 动态代理 Git YAML SpringBoot SpringMVC 回溯算法 分治算法 归并排序 快排 手撕 事务 MySQL索引 MySQL 小技巧 Spring Framework Spring 动态规划 Linux Android 贪心算法 操作系统 进程调度模拟 IPv6 数据库 计算机组成原理 计算机基础 栈 Java 静态路由 路由器 交换机 数字通信 网络工程 计算机网络 Web http 大学学习技巧 程序设计 算法

力扣12题-整数转罗马数字-贪心

发表于 2022-03-10 | 分类于 力扣刷题 | 0 | 阅读次数 125

题目描述

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

题目评估

知识点:哈希表、数学、字符串
官方难度:中等

分析

按照贪心算法,从当前阿拉伯数字的最高阶比较是否大于当前罗马数字的阶,然后算出有多少个罗马数字阶的整数倍。比如2820最高阶是2000,那就循环比较有几个M,2000有两个M,然后比较800是否大于500,然后加一个D,然后减去500计算300有几个100,加上3个C,下边以此类推。
参考的优质题解

Java代码题解

class Solution {
    public String intToRoman(int num) {
        StringBuilder res = new StringBuilder();
        int[] arabicNums = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] romanNums = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

        for (int i = 0; i < arabicNums.length; i++) {
            while (num >= arabicNums[i]) {
                res.append(romanNums[i]);
                num -= arabicNums[i];
            }
            if (num == 0) {
                break;
            }
        }
        return res.toString();
    }
}

复杂度分析

时间复杂度:O(1)。最坏条件下,循环的次数为哈希表的长度。
空间复杂度:O(1)。

# 算法 # 程序设计 # 力扣
Spring注解学习[email protected]注解
力扣13题-罗马数字转整数
  • 文章目录
  • 站点概览
优律

优律

优律的知识库

77 日志
20 分类
44 标签
E-mail Twitter Instagram
Links
  • CZLisyx - 浮生志
  • Vedfolnir
0%
© 2019 — 2023 萤火小屋——优律的博客网站
网站已勉强运行 
Halo博客系统技术支持