資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究字典序第 K 小的字串，其中包含 'a' X 次和 'b' Y 次
字典序第 K 小的字串，其中包含 'a' X 次和 'b' Y 次，是一個我們需要找到包含 X 個 'a' 和 Y 個 'b' 的第 K 小的字串的問題。這些字串按字典序排列，這意味著當我們對所有可能的字串進行排序時，最小的字串排在最前面。
在本教程中，我們將討論如何使用 C++ 解決此問題。我們將首先詳細瞭解問題陳述，然後介紹演算法方法。然後，我們將繼續使用動態規劃在 C++ 中實現解決方案。程式碼將進行詳細解釋，並逐步介紹解決問題的步驟。在本教程結束時，您將清楚地瞭解如何解決此問題以及在 C++ 中的實現細節。所以讓我們開始吧！
問題陳述
目標是識別按字典序排列的第 K 小的字串，該字串由 X 個字元 'a' 和 Y 個字元 'b' 組成。此問題的輸入是三個非負整數 X、Y 和 K。
示例 1
輸入
X=2, Y=3, K=3
輸出
abbab
解釋：包含 2 個 'a' 和 3 個 'b' 的字典序前三個最小的字串是 "aabbb"、"ababb" 和 "abbab"。因此，第三個字典序最小的字串是 "abbab"。
示例 2
輸入
X=4, Y=3, K=4
輸出
aaabbba
解釋：包含 4 個 'a' 和 3 個 'b' 的字典序第四個最小的字串是 "aaabbba"。
演算法
步驟 1. 建立一個名為 ‘fillDpArray’ 的函式，該函式接收引數 ‘X’、‘Y’、‘dp[][MAX]’、‘rows’ 和 ‘cols’
使用 ‘memset’ 將整個 ‘dp’ 陣列填充為 0。
將 ‘dp[0][0]’ 設定為 1。
使用巢狀迴圈遍歷 ‘dp’ 陣列
對於每個元素 ‘dp[i][j]’，透過新增 ‘dp[i - 1][j]’ 和 ‘dp[i][j - 1]’ 的值來更新其值。
步驟 2. 建立一個名為 ‘findKthString’ 的遞迴函式，該函式接收引數 ‘X’、‘Y’、‘K’ 和 ‘dp[][MAX]’
處理基本情況
如果 ‘X’ 為 0，則返回一個長度為 ‘Y’ 的 'b' 字串。
如果 ‘Y’ 為 0，則返回一個長度為 ‘X’ 的 'a' 字串。
檢查 ‘K’ 是否小於或等於 ‘dp[X - 1][Y]’
如果為真，則返回字元 'a' 與呼叫 ‘findKthString’ 並傳入引數 ‘X - 1’、‘Y’、‘K’ 和 ‘dp’ 的結果的串聯。
否則
返回字元 'b' 與呼叫 ‘findKthString’ 並傳入引數 ‘X’、‘Y - 1’、‘K - dp[X - 1][Y]’ 和 ‘dp’ 的結果的串聯。
步驟 3. 在 ‘main’ 函式中
宣告變數 ‘X’、‘Y’ 和 ‘K’ 以儲存使用者輸入。
從使用者處讀取 ‘X’、‘Y’ 和 ‘K’ 的輸入值。
驗證輸入值以確保它們滿足所需條件 ‘(X >= 0, Y >= 0, and K > 0)’。
建立一個二維陣列 ‘dp[MAX][MAX]’。
如果輸入值有效，則呼叫 ‘fillDpArray’ 函式並傳入引數 ‘X’、‘Y’、‘dp’、‘MAX’ 和 ‘MAX’ 以計算 ‘dp’ 陣列。
檢查輸入值是否有效以及 ‘K’ 是否小於或等於 ‘dp[X][Y]’
如果為真，則呼叫 ‘findKthString’ 函式並傳入引數 ‘X’、‘Y’、‘K’ 和 ‘dp’ 以獲取字典序第 K 小的字串。
透過列印從 ‘findKthString’ 獲得的字串來顯示結果。
否則，顯示錯誤訊息，指示輸入值無效。
現在，讓我們藉助示例檢視使用 C++ 實現上述演算法。
示例
使用 C++ 實現上述演算法
下面的 C++ 程式計算由 'a' 和 'b' 組成的字典序第 K 小的字串。它使用動態規劃來填充一個二維陣列 ‘dp’，其中包含每個 'a' 和 'b' 組合的有效字串計數。‘fillDpArray’ 函式初始化陣列並根據先前值更新其值。‘findKthString’ 函式透過遞迴檢查 ‘dp’ 中以 'a' 開頭的字串的計數，並使用更新的值遞迴呼叫自身來構造第 K 個字串。‘main’ 函式讀取輸入值，驗證它們，如果輸入有效則使用 ‘fillDpArray’ 計算結果，並顯示結果或錯誤訊息。
#include <iostream>
#include <cstring>
const int MAX = 30;
// Function to fill a 2D dp array with 0s
void fillDpArray(int X, int Y, int dp[][MAX], int rows, int cols) {
memset(dp, 0, rows * cols * sizeof(int));
dp[0][0] = 1;
// Traverse the dp array and update its values
for (int i = 0; i <= X; ++i) {
for (int j = 0; j <= Y; ++j) {
// Update the value of dp[i][j] based on previous values
if (i > 0) {
dp[i][j] += dp[i - 1][j];
}
if (j > 0) {
dp[i][j] += dp[i][j - 1];
}
}
}
}
// Recursive function to find the Kth lexicographically smallest string
std::string findKthString(int X, int Y, int K, int dp[][MAX]) {
// Handle base cases where the string has only one character
if (X == 0) {
return std::string(Y, 'b');
}
if (Y == 0) {
return std::string(X, 'a');
}
// If there are more than or equal to K strings which start with 'a',
//Then the first character is 'a'
if (K <= dp[X - 1][Y]) {
return std::string("a") + findKthString(X - 1, Y, K, dp);
}
// Otherwise, the first character of the resultant string is 'b'
else {
return std::string("b") + findKthString(X, Y - 1, K - dp[X - 1][Y], dp);
}
}
int main() {
// Input variables
int X=4, Y=3, K=4;
// Validate the input values to ensure they meet the required criteria
bool isValid = X >= 0 && Y >= 0 && K > 0;
// Calculate the result
int dp[MAX][MAX];
if (isValid) {
fillDpArray(X, Y, dp, MAX, MAX);
}
// Display the outcome or an error message
if (isValid && K <= dp[X][Y]) {
std::string kthString = findKthString(X, Y, K, dp);
std::cout << "The " << K << "th lexicographically smallest string with " << X << " 'a's and " << Y << " 'b's is: " << kthString << std::endl;
} else {
std::cout << "Invalid input values. Please enter non-negative integers for 'a's and 'b's, and a positive integer for K." << std::endl;
}
return 0;
}
輸出
The 4th lexicographically smallest string with 4 'a's and 3 'b's is: aaabbba
結論
總而言之，查詢具有給定 'a' 和 'b' 數量的字典序第 K 小的字串需要使用動態規劃。透過填充二維 DP 陣列並使用遞迴函式，我們可以找到字典序第 K 小的字串。此演算法的時間複雜度為 O(X * Y)，其中 X 和 Y 分別是 'a' 和 'b' 的數量。此演算法可以應用於需要查詢字典序第 K 小的字串的各種問題。
102 次檢視
