資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學根據給定關係形成的字典序最小字串
介紹
根據給定關係替換字元以生成字典序最小字串的任務，在字串處理中提出了一個引人入勝的挑戰。目標是根據所需的替換規則修改輸入字串中的字元，以獲得最小的字典序。在本文中，我們將重點關注使用C++解決這個問題。
我們將研究三種解決這個問題的方法，每種方法都使用獨特的技術和演算法方法。這些方法旨在提供對問題的不同理解，同時考慮效率、複雜性和易於執行等因素。
方法一：暴力法
暴力法包括透過根據給定關係替換字元來生成給定字串的所有可能排列。可以使用C++ STL中的`next_permutation`函式來生成排列。然後，我們將每個排列與當前字典序最小的字串進行比較，如果找到更小的排列，則更新它。
演算法
步驟1 − 初始化一個名為`smallest`的字串變數，其值為初始字串。
步驟2 − 建立初始字串的所有排列。
步驟3 − 對於每個排列，應用給定的關係並相應地替換字元。
步驟4 − 將調整後的排列與當前最小的字串進行比較，如果找到更小的字串，則更新它。
步驟5 − 重複步驟2-4，直到檢查完所有排列。
步驟6 − 返回最終的最小字串。
示例
#include <iostream>
#include <algorithm>
using namespace std;
string getLexicographicallySmallest(string str, string relation) {
string smallest = str;
sort(relation.begin(), relation.end());
do {
string temp = str;
for (int i = 0; i < relation.length(); i += 2) {
replace(temp.begin(), temp.end(), relation[i], relation[i + 1]);
}
if (temp < smallest) {
smallest = temp;
}
} while (next_permutation(str.begin(), str.end()));
return smallest;
}
int main() {
string str = "abccba";
string relation = "abcxyz";
string smallestString = getLexicographicallySmallest(str, relation);
cout << "Lexicographically Smallest String: " << smallestString << endl;
return 0;
}
輸出
Lexicographically Smallest String: abccba
方法二：貪婪法
貪婪法包括根據給定關係迭代地替換字串中的字元。我們從最左邊的字元開始，檢查是否存在更小的字元可用於替換。如果存在，我們替換它並繼續該過程，直到無法進行更多替換。
演算法
步驟1 − 從左到右遍歷初始字串。
步驟2 − 對於每個字元，檢查在給定關係中是否存在更小的替換字元。
步驟3 − 如果找到更小的字元，則替換當前字元。
步驟4 − 呼叫`getLexicographicallySmallest()`函式，並將結果值傳遞給名為`smalleststring`的變數。
步驟5 − 將調整後的字串作為字典序最小字串返回。
示例
#include <iostream>
#include <algorithm>
using namespace std;
string getLexicographicallySmallest(string str, string relation) {
sort(relation.begin(), relation.end());
for (int i = 0; i < str.length(); i++) {
for (int j = 0; j < relation.length(); j += 2) {
if (str[i] == relation[j] && relation[j + 1] < str[i]) {
str[i] = relation[j + 1];
}
}
}
return str;
}
int main() {
string str = "abccba";
string relation = "abcxyz";
string smallestString = getLexicographicallySmallest(str, relation);
cout << "Lexicographically Smallest String: " << smallestString << endl;
return 0;
}
輸出
Lexicographically Smallest String: abccba
方法三：優先佇列法
優先佇列法包括使用優先佇列根據給定關係以排序的方式儲存字串的字元。我們遍歷字串的字元並將它們入隊到優先佇列中。然後，我們從優先佇列中出隊字元並構建字典序最小字串。
演算法
步驟1 − 初始化一個優先佇列，用於根據給定關係以排序的方式儲存字元。
步驟2 − 將初始字串的所有字元入隊到優先佇列中。
步驟3 − 遍歷初始字串的字元。
步驟4 − 對於每個字元，從優先佇列中出隊最小的字元，並將其與原始字串中的字元進行比較。
步驟5 − 如果在給定關係中存在更小的替換字元，則將其入隊到優先佇列中。
步驟6 − 重複步驟4-5，直到處理完所有字元。
步驟7 − 透過從優先佇列中出隊所有字元來構建字典序最小字串。
步驟8 − 反轉字串以獲得正確的順序。
步驟9 − 返回字典序最小字串。
示例
#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <vector>
using namespace std;
string getLexicographicallySmallest(string str, string relation) {
vector<char> replacements(26, '#'); // Initialize replacements with a placeholder character '#'
for (int i = 0; i < relation.length(); i += 2) {
char curr = relation[i];
char repl = relation[i + 1];
if (replacements[curr - 'a'] == '#') {
replacements[curr - 'a'] = repl;
} else {
replacements[curr - 'a'] = min(replacements[curr - 'a'], repl);
}
}
for (int i = 0; i < str.length(); i++) {
if (replacements[str[i] - 'a'] != '#' && replacements[str[i] - 'a'] < str[i]) {
str[i] = replacements[str[i] - 'a'];
}
}
return str;
}
int main() {
string str = "abccba";
string relation = "abcxyz";
string smallestString = getLexicographicallySmallest(str, relation);
cout << "Lexicographically Smallest String: " << smallestString << endl;
return 0;
}
輸出
Lexicographically Smallest String: abccba
結論
總之，我們研究了三種不同的C++方法，這些方法透過根據某些關係替換字元來生成字典序最小的字串。暴力法生成所有排列，貪婪法迭代地替換字元，優先佇列法使用優先佇列來構建最小的字串。儘管方法不同，但給定的輸入在所有方法中都一致地生成了相同的輸出“abccba”。每種方法都有其優點，根據問題的限制和輸入大小，可能適合不同的場景。理解和實現這些方法可以有效地解決與基於某些關係的字串操作相關的類似問題。
瀏覽量：1000+
