现在位置: 首页 / 学习 / leetcode / 正文

LeetCode第十二题：整数转罗马数字

  • admin
  • 学习
  • 2024-02-21
  • 48热度
  • 0评论

题目来源：LeetCode第十二题

1.题目描述

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

提示：

  • 1 <= num <= 3999

2.解题思路

解法一：硬编码数字

  • 描述：根据罗马数字规则来对每一位的数字构建字符串，创建4个字符串数组来分别表示每一位可能的数字，范围是0-3999。通过除法和取模来获取每一位的数字，通过这个数字来查找对应的罗马数字组合起来。
  • 时间复杂度：O(1)，转换过程涉及对输入数字的处理，包括几次除法和取模运算。这些操作的时间复杂度是常数时间。
  • 空间复杂度：O(1)，四个罗马数字数组占用的空间是固定的，不随输入数字的大小而变化。
  • 参考代码：

java版：

class Solution {
    public String intToRoman(int num) {
        // 根据数据范围0-3999，千位M为1000-3000，百位C为100-900，十位X为10-90，个位I为0-9
        String M[] = { "", "M", "MM", "MMM" };
        String C[] = { "", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM" };
        String X[] = { "", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC" };
        String I[] = { "", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX" };

        // 取出每一位的数字，去上面的数组中找到对应的罗马数字
        String thousands = M[num / 1000];
        String hundreds = C[(num % 1000) / 100];
        String tens = X[(num % 100) / 10];
        String ones = I[num % 10];

        // 将结果组合起来
        String result = thousands + hundreds + tens + ones;

        return result;
    }
}

C++版：

class Solution {
public:
	string intToRoman(int num) {
		// 根据数据范围0-3999，千位M为1000-3000，百位C为100-900，十位X为10-90，个位I为0-9
		string M[] = { "", "M", "MM", "MMM" };
		string C[] = { "", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM" };
		string X[] = { "", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC" };
		string I[] = { "", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX" };

		// 将整数分解为千位、百位、十位和个位
		string thousands = M[num / 1000];
		string hundreds = C[(num % 1000) / 100];
		string tens = X[(num % 100) / 10];
		string ones = I[num % 10];

		// 将分解得到的罗马数字组合起来
		return thousands + hundreds + tens + ones;
	}
};

C版：

char* intToRoman(int num) {
	// 罗马数字的字符表示
	char* M[] = { "", "M", "MM", "MMM" };
	char* C[] = { "", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM" };
	char* X[] = { "", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC" };
	char* I[] = { "", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX" };

	// 分配足够的空间来存储结果字符串
	char* result = (char*)malloc(16 * sizeof(char));
	if (result == NULL) {
		return NULL; // 内存分配失败
	}

	// 构建罗马数字
	strcpy(result, M[num / 1000]);
	strcat(result, C[(num % 1000) / 100]);
	strcat(result, X[(num % 100) / 10]);
	strcat(result, I[num % 10]);

	return result;
}

解法二：递归法

  • 描述：从最大的罗马字符开始，逐步减少整数的值，并构建对应的罗马字符串，关键在于每次递减选择合适的罗马字符，并在整数归0时停止递归。
  • 时间复杂度：O(1)。n是输入数值转换成罗马数字所需的字符数。这题可以看作是常数。
  • 空间复杂度：O(1)。所需的额外空间都是常量大小。
  • 参考代码：

java版：

class Solution {
    // 罗马数字和其对应的整数值
    private static final int[] VALUES = { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 };
    private static final String[] SYMBOLS = { "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" };

    public String intToRoman(int num) {
        StringBuilder roman = new StringBuilder();
        return intToRomanHelper(num, roman, 0);
    }

    // 递归辅助方法
    private String intToRomanHelper(int num, StringBuilder roman, int index) {
        // 如果值为零，结束递归
        if (num == 0) {
            return roman.toString();
        }

        // 当前的数字大于等于索引指向的数字，循环在后面添加索引对应的罗马数字，添加一个就减去对应的值
        // 如2001，index=0，VALUES[index]=1000， 加M 后-1000=1001，继续加M后-1000=1，不满足条件
        while (num >= VALUES[index]) {
            roman.append(SYMBOLS[index]);
            num -= VALUES[index];
        }

        // 进行下一个索引的递归
        return intToRomanHelper(num, roman, index + 1);
    }
}

C++版：

class Solution {
public:
	// 罗马数字和其对应的整数值
	const int values[13] = { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 };
	const string symbols[13] = { "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" };

	string intToRoman(int num) {
		string roman;
		intToRomanHelper(num, roman, 0);
		return roman;
	}

private:
	// 递归辅助方法
	void intToRomanHelper(int num, string& roman, int index) {
		// 如果值为零，结束递归
		if (num == 0) {
			return;
		}
		// 当前的数字大于等于索引指向的数字，循环在后面添加索引对应的罗马数字，添加一个就减去对应的值
		// 如2001，index=0，VALUES[index]=1000， 加M 后-1000=1001，继续加M后-1000=1，不满足条件
		while (num >= values[index])
		{
			roman += symbols[index];
			num -= values[index];
		}
		// 进行下一个索引的递归
		intToRomanHelper(num, roman, index + 1);
	}
};

C版：

// 罗马数字的值和对应的符号
const int values[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
const char* symbols[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

// 递归函数原型声明
void intToRomanHelper(int num, char* roman, int index);

// 将整数转换为罗马数字的主要函数
char* intToRoman(int num) {
    // 分配足够的空间来存储最终的罗马数字字符串
    char* roman = (char*)malloc(20 * sizeof(char)); // 确保有足够的空间
    if (roman == NULL) {
        return NULL; // 内存分配失败
    }
    roman[0] = '\0'; // 初始化为空字符串
    intToRomanHelper(num, roman, 0);
    return roman;
}

// 递归辅助函数
void intToRomanHelper(int num, char* roman, int index) {
    if (num == 0) {
        return; // 递归的基本情况
    }
    while (num >= values[index]) {
        strcat(roman, symbols[index]); // 添加符号到字符串末尾
        num -= values[index]; // 减去已经表示的数值
    }
    intToRomanHelper(num, roman, index + 1); // 递归处理剩余的数字
}

解法三：贪心法

  • 描述：列一个包含所需的罗马字符和对应的数字表，每一次都从从可能的罗马数字表示中选取最大的一个，使得这个罗马数字的值不超过当前的整数值，每一步尽可能地减少剩余的整数值，直到整数变为0。对于当前剩余的整数值，算法不考虑后续的选择，只关注如何通过添加一个最大的罗马数字来减少这个整数。体现了贪心的思想
  • 时间复杂度：O(1)。
  • 空间复杂度：O(1)。
  • 参考代码：

java版：

class Solution {
    // 罗马数字表示及其对应的整数值
    private int[] values = { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 };
    private String[] symbols = { "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" };

    public String intToRoman(int num) {
        StringBuilder roman = new StringBuilder();
        // 从最大的罗马数字开始尝试
        for (int i = 0; i < values.length; i++) {
            // 当前整数可以包含多少个当前罗马数字
            while (num >= values[i]) {
                num -= values[i];
                roman.append(symbols[i]);
            }
            // 如果已经完全转换，则结束循环
            if (num == 0) {
                break;
            }
        }
        return roman.toString();
    }
}

C++版：

class Solution {
public:
	string intToRoman(int num) {
		// 罗马数字的字符表示和对应的整数值
		vector<pair<int, string>> romanNumerals = {
			{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"}
		};

		string result = "";
		// 遍历每个罗马数字表示
		for (const auto& pair : romanNumerals) {
			// 当前数字可以使用当前罗马数字的次数
			while (num >= pair.first) {
				// 将罗马数字加到结果中
				result += pair.second;
				// 减去已经表示的数值
				num -= pair.first;
			}
		}
		return result;
	}
};

C版：

// 定义一个结构体来存储整数值和对应的罗马数字
typedef struct {
	int value;
	char* numeral;
} RomanNumeral;

// 将整数转换为罗马数字的函数
char* intToRoman(int num) {
	static RomanNumeral romanNumerals[] = {
		{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"}
	};
	// 用于存储结果的静态字符数组，足够大以容纳最长的罗马数字
	static char result[64];
	int i;

	// 初始化结果字符串为空
	strcpy(result, "");

	// 遍历所有罗马数字
	for (i = 0; i < sizeof(romanNumerals) / sizeof(RomanNumeral); ++i) {
		// 当当前数值小于等于num时，添加对应的罗马数字到结果字符串
		while (num >= romanNumerals[i].value) {
			strcat(result, romanNumerals[i].numeral);
			num -= romanNumerals[i].value;
		}
	}

	return result;
}