分库查询 TensorRT jsp json laravel authentication magento search layout datatable orm swiper vue中文网 vue表单提交 react视频教程 nodejs视频教程 seo教程下载 flink教程视频 bootstrap侧边栏 matlab注释一段 mysql更新多个字段 bitlocker加密好慢 ubuntu显示隐藏文件夹 bootstrap居中对齐 js基本数据类型有哪些 完美解决cpu利用率低 普通话网上报名 python指令 python函数的调用 java使用正则表达式 java取当前时间 java怎么编程 java的date 隐藏虚拟键 图片生成网址 dll之家 战斗的召唤 win10有几个版本 maya2016教程 lol卡米尔
当前位置: 首页 > 学习教程  > 编程语言

12. 整数转罗马数字

2021/1/13 20:34:08 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

12. 整数转罗马数字 题目描述 罗马数字包含以下七种字符: I, V, X, L,C,D 和 M。 字符 数值 I 1 V 5 X 10 L 50 C 100 D …

12. 整数转罗马数字

题目描述

罗马数字包含以下七种字符: IVXLCDM

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如, 罗马数字 2 写做 II ,即为两个并列的 I。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 的范围内。

示例1
输入: 3
输出: "III"
示例2
输入: 4
输出: "IV"
示例3
输入: 9
输出: "IX"
示例4
输入: 58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.
示例5
输入: 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.

题解:

模拟题。

罗马数字的计数方法如下:

  1. 相同的数字连写,所表示的数字等于这些数字相加的和,比如:MMM = 3000;
  2. 小的数字在大的数字右边,所表示的数字等于这些数字相加的和,比如:XII = 22;
  3. 几个特殊的数字可以小的在大的右边,仅限于:IV、IX、XL、XC、CD和CM,所表示的数字等于大数减小数得到的结果,例如:IX = 9;
  4. 正常使用时,连写的数字重复不得超过三次

如果我们将 IV、IX、XL、XC、CD 和 CM 看做新单位,加入到基本单位中,那么就可以将目标值看做这些单位相加的和,且同一种单位不能使用超过3次。

M	 CM	  D	  CD  C	  XC L	XL	X	IX	V	IV	I
1000 900  500 400 100 90 50	40	10	9	5	4	1

在相加时,优先选用值较大的单位即可。

时间复杂度:罗马数字和阿拉伯数字的长度是一个数量级的,都是 O ( l o g n ) O(logn) O(logn)

代码:

class Solution {
public:
    string intToRoman(int num) {
        int val[] = { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        string key[] = { "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" };
        string ret = "";
        int d, j;
        for ( int i = 0; i < 13; ++i ) {
            if ( num < val[i] ) continue;
            d = num / val[i];
            for ( j = 0; j < d; ++j) ret += key[i];
            num %= val[i];
        }
        return ret;
    }
};
/*
时间:8ms,击败:77.80%
内存:5.7MB,击败:99.71%
*/

本文链接: http://www.dtmao.cc/news_show_600359.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?