数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会研究
服装研究
法律研究通过重新排列给定字符串的字符来获得最大的罗马数字
这些字符代表罗马数字：'I'、'V'、'X'、'L'、'C'、'D' 和 'M'。我们将得到一个可能还包含其他字符的字符串（所有字符都将是大写英文字母），我们必须找到通过改变给定字符串字符的位置所能获得的最大罗马数字。如果无法得到罗马数字，则返回“无效”作为答案。
输入1
string str = “VICML”
输出
MCLVI
解释
在给定的字符串中，M 的值最大，其次是 C，然后所有字符的值都以降序排列，因此我们只需以降序打印它。
输入
"MLCIU"
输出
Invalid
解释
在给定的字符串中，包含字符 'U'，它不是罗马数字中的字符。因此，我们将返回字符串“无效”。
方法
我们已经看到了上面的例子，现在让我们来看一下实现部分。
为了实现所需的代码，我们将创建许多函数，这些函数将帮助我们找到我们需要的特定的一组事物/值。
首先，该函数用于查找罗马字符的值，并确定当前字符是否是有效的罗马字符。此函数将单个字符作为输入，如果它是有效的，则返回字符的值，否则返回 -1。
下一个函数是将罗马数字字符串转换为十进制数字。此函数将单个字符串作为参数，并返回一个整数作为返回值。
我们将有一个与前一个函数类似的函数，但正好相反，即十进制转罗马数字，此函数将十进制或整数值作为参数，并返回表示罗马值的字符串。
我们将使用 sort 函数对字符串进行排序，并将使用 compare 函数更新 sort 函数，以便以降序排列字符。
需要一个辅助函数来遍历字符串以查找字符串是否有效，然后对当前字符串进行排序。之后，我们将使用这些函数检查当前字符串值的十进制表示。
示例
#include <bits/stdc++.h>
using namespace std;
// function to create the value of Roman characters if the character is not present in Roman then return -1
int romanVal(char ch){
if (ch == 'I'){
return 1;
}
else if (ch == 'X'){
return 10;
}
else if (ch == 'V'){
return 5;
}
else if (ch == 'D'){
return 500;
}
else if(ch == 'C'){
return 100;
}
else if(ch == 'L'){
return 50;
}
else if(ch == 'M'){
return 1000;
}
else{
// given number is invalid
return -1;
}
}
// function to get the decimal value from the given Roman value
int romanToDec(string str){
int ans = 0; // variable to store the final answer
int len = str.size(); // length of the final string
ans = romanVal(str[len - 1]); // initializing the value of result variable
// Traversing over the given string
for (int i = len - 2; i>= 0; i--){
if (romanVal(str[i]) <romanVal(str[i + 1])){
ans -= romanVal(str[i]);
}
else{
ans += romanVal(str[i]);
}
}
return ans; // return the final answer
}
// function for converting the decimal value to roman
string decToRoman(int num){
string ans = ""; // variable to store the final answer
// array to store all the numeric values that can be represented in the roman
int decVals[] = {1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000};
// array to store all the roman values that equivalent to the given decimal values
string romVals[] = { "I", "IV", "V", "IX", "X", "XL", "L", "XC", "C", "CD" , "D", "CM", "M" };
int idx = 12; // starting from the last index
while (num> 0){
int cur = num / decVals[idx];
num = num % decVals[idx];
while (cur--) {
ans += romVals[idx];
}
idx--;
}
return ans; // return the final answer
}
// compare function to sort the string in the decreasing order
bool cmp(char a, char b){
// getting values of both the current characters
int val_a = romanVal(a);
int val_b = romanVal(b);
return (val_a>val_b);
}
// creating function to find the largest possible result
string findString(string str){
// traversing over the string to check if any invalid character is present or not
for(int i=0; i<str.length(); i++){
if(romanVal(str[i]) == -1){
// if romalValue is -1 means chracter is invalid
return "Invalid";
}
}
sort(str.begin(), str.end(), cmp);
int num = romanToDec(str);
string rom = decToRoman(num);
if (str != rom){
return "Invalid";
}
return rom; // returning the result
}
int main(){
string str = "VICML"; // given string
cout << "Given String: " << str << endl;
cout << "Largest Roman Numeral possible by rearranging characters of a given string: ";
// calling to the function
cout<<findString(str)<<endl;
return 0;
}
输出
Given String: VICML Largest Roman Numeral possible by rearranging characters of a given string: MCLVI
时间和空间复杂度
上述代码的时间复杂度为 O(N*log(N))，其中 N 是给定字符串的大小。
上述代码的空间复杂度为 O(N)，因为我们使用另一个字符串来存储结果。
结论
在本教程中，我们实现了一个程序，通过更新字符的位置来查找表示最大可能罗马数字的字符串。如果给定的字符串无效，则可以返回“无效”作为答案。我们实现的代码的时间复杂度为 O(N*log(N))，空间复杂度为 O(N)。
浏览量：111
