题目描述:给定一个整数,将其转换为罗马数字。罗马数字由七个字符表示:I(1)、V(5)、X(10)、L(50)、C(100)、D(500)和M(1000)。通常情况下,小的数字位于大的数字的右边。但有特殊情况,如4表示为IV(5-1),9表示为IX(10-1),40表示为XL(50-10),90表示为XC(100-10),400表示为CD(500-100),900表示为CM(1000-100)。编写一个程序,将给定的整数转换为相应的罗马数字表示。
示例:
输入: num = 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.
方法1 模拟(来源于力扣官解)
思路:给定一个数字number,找到不超过该数字的罗马符号对应的值(这个值应为最大的那个),比如1100这个数字,为1000;888则为500;然后循环往复,按这个套路一直减,然后得到的对应罗马符号挨个拼起来,直到无法再减,也就是他喵的这个数字最后为0,停止运行,下面以特定的数字进行演示,如下图所示:
c++完整代码:
#include<iostream>
#include<vector>
using namespace std;
//创建一个名为valueSymbols的pair,并进行初始化
const pair<int, string> valueSymbols[] = {
{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"},
};
class Solution{
public:
string intToRoman(int num){
string roman;
for(const auto &[value,symbol]:valueSymbols){
while(num > value){
num -= value; //当前数减去特定的罗马字符对应的数字
roman += symbol; //罗马字符进行累加
}
if(num == 0){ //当前数字为0时
break;
}
}
return roman;//返回罗马字符
}
};
int main(){
int number = 3333;
Solution solution;
std::string roman = solution.intToRoman(number);
std::cout << number << "into roman digital: " << roman <<endl;//输出结果
return 0;
}
//创建一个名为valueSymbols的pair,并进行初始化
const pair<int, string> valueSymbols[] = {
{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"},
};
class Solution{
public:
string intToRoman(int num){
string roman;
for(const auto &[value,symbol]:valueSymbols){
while(num > value){
num -= value; //当前数减去特定的罗马字符对应的数字
roman += symbol; //罗马字符进行累加
}
if(num == 0){ //当前数字为0时
break;
}
}
return roman;//返回罗马字符
}
};
java完整代码:
public class IntToRoman {
// 定义罗马数字的值和对应的符号
int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
// 将整数转换为罗马数字的方法
public String intToRoman(int num) {
//StringBuffer 是 Java 中的一个类,用于处理可变的字符序列。
//与 String 类不同,StringBuffer 的长度和内容可以被修改,而不需要创建新的对象。
//这使得 StringBuffer 在需要频繁修改字符串的情况下更为高效,因为它避免了创建大量临时对象
//常用方法:
//append(String str): 将指定的字符串追加到当前字符串的末尾
//insert(int offset, String str): 在指定位置插入指定的字符串
//delete(int start, int end): 删除指定范围内的字符
//replace(int start, int end, String str): 用新字符串替换指定范围内的字符
//reverse(): 反转字符串的内容
//toString(): 将 StringBuffer 对象转换为字符串
StringBuffer roman = new StringBuffer();
for (int i = 0; i < values.length; ++i) {
int value = values[i];
String symbol = symbols[i];
// 循环将当前值的符号加入结果,直到整数小于当前值
while (num >= value) {
num -= value;
roman.append(symbol);//将指定的字符串追加到当前字符串的末尾
}
// 如果整数为0,结束循环
if (num == 0) {
break;
}
}
return roman.toString(); //将 StringBuffer 对象转换为字符串
}
// 主函数,用于测试整数转换为罗马数字
public static void main(String[] args) {
IntToRoman converter = new IntToRoman(); // 创建 IntToRoman 类的实例
int number = 3333;
String roman = converter.intToRoman(number);
System.out.println(number + " 转换成罗马数字为: " + roman);
}
}
public class IntToRoman {
// 定义罗马数字的值和对应的符号
int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
// 将整数转换为罗马数字的方法
public String intToRoman(int num) {
//StringBuffer 是 Java 中的一个类,用于处理可变的字符序列。
//与 String 类不同,StringBuffer 的长度和内容可以被修改,而不需要创建新的对象。
//这使得 StringBuffer 在需要频繁修改字符串的情况下更为高效,因为它避免了创建大量临时对象
//常用方法:
//append(String str): 将指定的字符串追加到当前字符串的末尾
//insert(int offset, String str): 在指定位置插入指定的字符串
//delete(int start, int end): 删除指定范围内的字符
//replace(int start, int end, String str): 用新字符串替换指定范围内的字符
//reverse(): 反转字符串的内容
//toString(): 将 StringBuffer 对象转换为字符串
StringBuffer roman = new StringBuffer();
for (int i = 0; i < values.length; ++i) {
int value = values[i];
String symbol = symbols[i];
// 循环将当前值的符号加入结果,直到整数小于当前值
while (num >= value) {
num -= value;
roman.append(symbol);//将指定的字符串追加到当前字符串的末尾
}
// 如果整数为0,结束循环
if (num == 0) {
break;
}
}
return roman.toString(); //将 StringBuffer 对象转换为字符串
}
}
Python完整代码:
class Solution:
# 创建一个名为value_symbols的列表,并进行初始化
value_symbols = [
(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"),
]
def intToRoman(self, num):
roman = list()
for value, symbol in Solution.value_symbols:
while num >= value:
num -= value # 当前数减去特定的罗马字符对应的数字
roman.append(symbol) # 在列表后添加罗马字符
if num == 0: # 当前数字为0时
break
return "".join(roman) # 返回罗马字符
number = 3333 # 设置当前数字
solution = Solution() # 实例化
result = solution.intToRoman(number)
print("整数转罗马数字为:", result)
class Solution:
# 创建一个名为value_symbols的列表,并进行初始化
value_symbols = [
(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"),
]
def intToRoman(self, num):
roman = list()
for value, symbol in Solution.value_symbols:
while num >= value:
num -= value # 当前数减去特定的罗马字符对应的数字
roman.append(symbol) # 在列表后添加罗马字符
if num == 0: # 当前数字为0时
break
return "".join(roman) # 返回罗马字符
方法2 硬编码(来源于力扣官解)
从上面模拟的方法我们可以看出,共有13组罗马符号,然后我们可以发现千位数字上有且仅有M这一种表示方法,当超过9999时,加入10001,也只是由10个M和1个I组成,百位上只可以由C、CD、D、CM组成,十位数字只能由X、XL、L、XC组成,个位数字只能由I、IV、V、IX组成,将这些数字组合成一个表:
可以看出每一位之上罗马符号都是不同的,因此可以采用“对号入座”的方法进行编码,相当于在千百十个位上分别求出对应的0 1 2 3 4 5 6 7 8 9,然后再去找到对应的罗马符号,最后返回得到的结果就ok了。那么怎样求出千百十个位上对应的数字呢?这时候就需要用到模运算和除法运算了:
以python为例:
c++完整代码:
#include <iostream>
using namespace std;
// 罗马数字的千位表示
const string thousands[] = {"", "M", "MM", "MMM", "MMMM", "MMMMM",
"MMMMMM", "MMMMMMM", "MMMMMMMM", "MMMMMMMMM"};
// 罗马数字的百位表示
const string hundreds[] ={"","C","CC","CCC","CD","D",
"DC","DCC","DCCC","CM"};
// 罗马数字的十位表示
const string tens[] = {"","X","XX","XXX","XL","L",
"LX","LXX","LXXX","XC"};
// 罗马数字的个位表示
const string ones[] = {"","I","II","III","IV","V",
"VI","VII","VIII","IX"};
// 定义 Solution 类
class Solution {
public:
// 将整数转换为罗马数字的方法
string intToRoman(int num) {
return thousands[num / 1000] +
hundreds[num % 1000 / 100] +
tens[num % 100 / 10] +
ones[num % 10];
}
};
// 主函数
int main() {
// 待转换的整数
int number = 9999;
// 创建 Solution 类的实例
Solution solution;
// 调用方法将整数转换为罗马数字
string roman = solution.intToRoman(number);
// 输出转换结果
cout << number << " 转换成罗马数字为: " << roman << endl;
// 返回执行成功
return 0;
}
java完整代码:
public class intToRoman1 {
// 罗马数字的千位表示
String[] thousands = {"", "M", "MM", "MMM", "MMMM", "MMMMM",
"MMMMMM", "MMMMMMM", "MMMMMMMM", "MMMMMMMMM"};
// 罗马数字的百位表示
String[] hundreds ={"","C","CC","CCC","CD","D",
"DC","DCC","DCCC","CM"};
// 罗马数字的十位表示
String[] tens = {"","X","XX","XXX","XL","L",
"LX","LXX","LXXX","XC"};
// 罗马数字的个位表示
String[] ones = {"","I","II","III","IV","V",
"VI","VII","VIII","IX"};
// 将整数转换为罗马数字的方法
public String intToRoman(int num){
StringBuffer roman = new StringBuffer();
roman.append(thousands[num / 1000]); // 千位
roman.append(hundreds[num % 1000 / 100]); // 百位
roman.append(tens[num % 100 / 10]); // 十位
roman.append(ones[num % 10]); // 个位
return roman.toString();
}
// 主函数,用于测试整数转换为罗马数字
public static void main(String[] args){
intToRoman1 converter = new intToRoman1(); // 创建 intToRoman1 类的实例
int number = 9999;
String roman = converter.intToRoman(number);
System.out.println(number + " 转换成罗马数字为: " + roman);
}
}
python完整代码:
class Solution:
# 罗马数字的千位表示
thousands = ["", "M", "MM", "MMM", "MMMM", "MMMMM",
"MMMMMM", "MMMMMMM", "MMMMMMMM", "MMMMMMMMM"]
# 罗马数字的百位表示
hundreds = ["", "C", "CC", "CCC", "CD", "D",
"DC", "DCC", "DCCC", "CM"]
# 罗马数字的十位表示
tens = ["", "X", "XX", "XXX", "XL", "L",
"LX", "LXX", "LXXX", "XC"]
# 罗马数字的个位表示
ones = ["", "I", "II", "III", "IV", "V",
"VI", "VII", "VIII", "IX"]
# 将整数转换为罗马数字的方法
def intToRoman(self, num):
return (Solution.thousands[num // 1000] +
Solution.hundreds[num % 1000 // 100] +
Solution.tens[num % 100 // 10] +
Solution.ones[num % 10])
# 设置当前数字
number = 3333
# 实例化 Solution 类
solution = Solution()
# 调用方法将整数转换为罗马数字
result = solution.intToRoman(number)
# 输出转换结果
print("整数转罗马数字为:", result)
方法3 贪心哈希表
具体算法的流程如下图所示:
python完整代码:
class Solution:
def intToRoman(self, num):
hashmap = {1000: "M", 900: "CM", 500: "D", 400: "CD",
100: "C", 90: "XC", 50: "L", 40: "XL", 10: "X",
5: "V", 4: "IV", 1: "I"}
roman = ''
for key in hashmap:
if num // key != 0: # 当前数字除以哈希表中对应的值不等于0时
count = num // key # 计算当前位上的数字(对应哈希中key的个数)
roman += hashmap[key] * count # 罗马符号进行累加
num %= key # 计算剩余的数
return roman
# 设置当前数字
number = 3333
# 实例化Solution类
solution = Solution()
# 调用方法将整数转换为罗马数字
result = solution.intToRoman(number)
# 输出转换结果
print("整数转罗马数字为:", result)
c++完整代码:
#include<iostream>
using namespace std;
class Solution{
public:
string intToRoman(int num){
int values[] = {1000, 900, 500, 400, 100, 90,
50, 40, 10, 9, 5, 4, 2, 1};
string romans[] = {"M", "CM", "D", "CD", "C", "XC",
"L", "XL", "X", "IX", "V", "IV", "I"};
string roman;
for(int i = 0;i < 13; i++){
while(num >= values[i]){
num -= values[i];
roman += romans[i];
}
}
return roman;
}
};
int main() {
// 待转换的整数
int number = 9999;
// 创建 Solution 类的实例
Solution solution;
// 调用方法将整数转换为罗马数字
string roman = solution.intToRoman(number);
cout << number << " into roman digital " << roman << endl;// 输出转换结果
return 0; // 返回执行成功
}
Java完整代码:
import java.util.HashMap;
public class intToRoman2 {
public String intToRoman(int num) {
HashMap<Integer, String> hashmap = new HashMap<>();
hashmap.put(1000, "M");
hashmap.put(900, "CM");
hashmap.put(500, "D");
hashmap.put(400, "CD");
hashmap.put(100, "C");
hashmap.put(90, "XC");
hashmap.put(50, "L");
hashmap.put(40, "XL");
hashmap.put(10, "X");
hashmap.put(9, "IX");
hashmap.put(5, "V");
hashmap.put(4, "IV");
hashmap.put(1, "I");
StringBuilder roman = new StringBuilder();
for (int key : hashmap.keySet()) {
while (num >= key) {
roman.append(hashmap.get(key));
num -= key;
}
}
return roman.toString();
}
public static void main(String[] args) {
// 设置当前数字
int number = 3333;
// 实例化 IntToRoman 类
IntToRoman converter = new IntToRoman();
// 调用方法将整数转换为罗马数字
String result = converter.intToRoman(number);
// 输出转换结果
System.out.println("整数转罗马数字为: " + result);
}
}