012. 整数转罗马数字 | Leetcode题解
16lz
2021-01-22
题目描述:
罗马数字包含以下七种字符：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到 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.
难度：
- 难度：中等
- 支持语言：JavaScript、Python、C++
相关标签
- 数学
- 字符串
相关企业
- 字节
- 微保
- 爱奇艺
复杂度分析
- 时间复杂度：由于左右指针移动的次数加起来正好是 n， 因此时间复杂度为 。
- 空间复杂度：。
思路 1（javascript）:
注意4和9的处理方式，由于9的罗马文需要用到10，
I(1),V(5),X(10)处理范围[1,9]；X(10),L(50),C(100)处理范围[10,90]；C(100),D(500),M(1000)处理范围[100,900]；
确定好处理范围后，对数字的每一位进行处理，再叠加字符串就是结果。
思路 2
- 找出所有不同的数字和罗马数字的对应组合
- 用两个数组分别列举
- 通过已知数字遍历values数组，相同等级的数字直接多次循环，字符串追加即可
思路 3
给定一个整数，将其转为罗马数字，输入数字在1到3999范围内。已知：罗马数字包含以下七种字符：I,V,X,L,C,D,M
//转换表为：字符 数值 进位 I 1 个位值为1 V 5 个位值为5 X 10 十位值为1 L 50 十位值为5 C 100 百位值为1 D 500 百位值为5 M 1000 千位值为1
由罗马数字表示规则可知
- 一般情况下 数字组成：大的数字位+小的数字位 ---- <1>
- 例如：6：VI 7:VII 8:VIII
- 可知：数值大小 == 大的数字位+小的数字位
- 再如：1:I 2:II 3: III
- 但当罗马数字进位值（个、十、百、千）== 9 或 == 4 时，数字组成变为：小的数字+大的数字 ---- <2>
// 例如：4:IV 9:IX 40:XL 90:XC 400:CD 900:CM
可知：数值大小 == 大的数字位-小的数字位
由上述可以推出罗马数字每个进位值1-9的表示法：
个位【1-9】：I、II、III、IV、V、VI、VII、VIII、IX （对应阿拉伯数字 X%10）
十位【1-9】：X、XX、XXX、XL、L、LX、LXX、LXXX、XC （对应阿拉伯数字 (X%100)/10）
百位【1-9】：C、CC、CCC、CD、D、DC、DCC、DCCC、CM （对应阿拉伯数字 (X%1000)/100）
千位【1-9】：M、MM、MMM （对应阿拉伯数字 X/1000）
由以上可知一个阿拉伯数字 => 罗马数字
num => num/1000 + (num%1000)/100 +(num%100)/10 + num%10
代码
JavaScript 实现
/**
* @来源：Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍：一个致力于帮助开发者用代码改变世界为使命的平台，每天都可以在这里找到技术世界的头条内容
* @param {number} num
* @return {string}
*/
var intToRoman = function(num) {
let bit={}
bit[0]=['I','V','X']
bit[1]=['X','L','C']
bit[2]=['C','D','M']
bit[3]=['M']
function toRoman(n,cur){
if(n===0)return ''
if(n<4)return cur[0].repeat(n)
if(n===4)return cur[0]+cur[1]
if(n<9)return cur[1]+cur[0].repeat(n-5)
if(n===9)return cur[0]+cur[2]
}
let str=num+''
let len=str.length
let res=''
let N=num
for(let i=len;i>=1;i--){
let curMod=Math.pow(10,i-1)
let n=Math.floor(N/curMod)
N %=curMod
res+=toRoman(n,bit[i-1])
}
return res
};
/**
作者：Alexer-660
链接：https://leetcode-cn.com/problems/integer-to-roman/solution/12-zheng-shu-zhuan-luo-ma-shu-zi-by-alexer-660/
* @param {number} num
* @return {string}
*/
var intToRoman = function(num) {
var Q = ["", "M", "MM", "MMM"];
var B = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"];
var S = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"];
var G = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"];
return Q[Math.floor(num/1000)] + B[Math.floor((num%1000)/100)] + S[Math.floor((num%100)/10)] + G[num%10];
};
C++ 实现
// 作者：z1m
// 链接：https://leetcode-cn.com/problems/integer-to-roman/solution/tan-xin-ha-xi-biao-tu-jie-by-ml-zimingmeng/
string intToRoman(int num) {
string table[4][10] = { // 1~9
{"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"},
// 10~90
{"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"},
// 100~900
{"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"},
// 1000~3000
{"", "M", "MM", "MMM"}
};
string result;
int count = 0;
while(num > 0){
int temp = num % 10;
result = table[count][temp] + result;
num /= 10;
count++;
}
return result;
}
// 作者：pinku-2
// 链接：https://leetcode-cn.com/problems/integer-to-roman/solution/zheng-shu-zhuan-luo-ma-shu-zi-cshi-xian-liang-chon/
#include <string>
#include <iostream>
#include <vector>
using namespace std;
class Solution
{
public:
string intToRoman(int num)
{
string result;
vector<string> tmpVec1 = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
vector<string> tmpVec2 = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
vector<string> tmpVec3 = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
vector<string> tmpVec4 = {"", "M", "MM", "MMM"};
vector<vector<string>> store = {tmpVec1, tmpVec2, tmpVec3, tmpVec4};
result.append(store[3][num / 1000 % 10]);
result.append(store[2][num / 100 % 10]);
result.append(store[1][num / 10 % 10]);
result.append(store[0][num % 10]);
return result;
}
};
Python 实现
# 作者：liweiwei1419
# 链接：https://leetcode-cn.com/problems/integer-to-roman/solution/tan-xin-suan-fa-by-liweiwei1419/
class Solution:
def intToRoman(self, num: int) -> str:
# 把阿拉伯数字与罗马数字可能出现的所有情况和对应关系，放在两个数组中
# 并且按照阿拉伯数字的大小降序排列，这是贪心选择思想
nums = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
romans = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
index = 0
res = ''
while index < 13:
# 注意：这里是等于号，表示尽量使用大的"面值"
while num >= nums[index]:
res += romans[index]
num -= nums[index]
index += 1
return res
# 作者：z1m
# 链接：https://leetcode-cn.com/problems/integer-to-roman/solution/tan-xin-ha-xi-biao-tu-jie-by-ml-zimingmeng/
class Solution:
def intToRoman(self, num: int) -> str:
# 使用哈希表，按照从大到小顺序排列
hashmap = {1000:'M', 900:'CM', 500:'D', 400:'CD', 100:'C', 90:'XC', 50:'L', 40:'XL', 10:'X', 9:'IX', 5:'V', 4:'IV', 1:'I'}
res = ''
for key in hashmap:
if num // key != 0:
count = num // key # 比如输入4000，count 为 4
res += hashmap[key] * count
num %= key
return res
其他
- 原题leetcode链接：https://leetcode-cn.com/problems/integer-to-roman/
- 合作方：JavaScript中文网 – 全球极客挚爱的技术成长平台
- 说明：leetcode 题解 | 每日一题
更多相关文章
- 使用数字作为javascript对象元素的名称
- jQuery+EasyUI实现treegrid/datagride所绑定列只能够输入数字，且
- js限制文本框只能输入数字方法
- phpcms日期--汉字与数字的转换
- php实现完整版验证码（数字+大小写字母+干扰素）
- PHP中是否存在“clamp”数字函数?
- mysql_fetch_array返回一个数组，数字为“1”
- php 从指定数字中获取随机组合的方法
- PHP是否以不同方式（内部）处理数字索引数组？
随机推荐