資料結構
網路
關係資料庫管理系統 (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
