資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究從給定陣列中根據給定條件選擇字串後，字串的最大長度
在這個問題中，我們需要找到透過將陣列字串附加到結果字串中獲得的結果字串的最大長度，前提是如果我們選擇長度為 x 的字串，則可以選擇接下來的 x/2 個字串。
我們可以使用遞迴函式、記憶化和動態規劃方法來解決該程式設計問題。
問題陳述 - 我們給定一個名為 str_array 的字串陣列，其中包含 N 個字串。我們需要新增陣列中給定的字串並找到結果字串的最大大小。在將字串附加到結果字串時，我們需要遵循以下規則：如果我們選擇任何長度為 x 的字串，則不能從陣列中選擇接下來的 x/2 個字串。
示例
輸入
str_array[] = {"tutor", "po", "nt", "welco", "ghj"}
輸出
10
解釋 - 我們可以選擇“tutor”和“welco”字串。
輸入
str_array[] = {"tu", "po", "nt", "wel", "ghj"}
輸出
7
解釋 - 我們可以選擇“tu”、“nt”和“ghj”字串。結果字串的長度將為 7。
輸入
str_array[] = {"tutorialspoint", "po", "nt", "wel", "ghj"};
輸出
14
解釋 - 我們只能選擇“tutorialspoint”字串。
為了解決這個問題，我們需要對字串做出總共 2N 個選擇，並根據選擇的結果選擇具有最大長度的最終答案。
方法 1
在這種方法中，我們將建立一個遞迴函式來考慮字串的所有選擇，並根據所有選擇，我們將選擇最大長度。
演算法
步驟 1 - 首先，定義基本情況。如果陣列長度小於開始位置，則返回 0。
步驟 2 - 現在，我們必須對當前字串做出選擇。第一個選項是包含該字串。如果我們包含該字串，則將字串大小新增到遞迴函式返回的值中。此外，更改開始引數值，因為我們不能選擇接下來的 x/2 長度，其中 x 是字串長度。
步驟 3 - 如果我們不包含當前字串，則在將開始引數值加 1 後進行遞迴函式呼叫。
步驟 4 - 從 sol1 和 sol2 中取最大值並返回它。
示例
#include <bits/stdc++.h>
using namespace std;
int maxStringSize(string str_array[], int len, int start) {
// Return 0 if start exceeds len
if (start >= len)
return 0;
// If value is not calculated for start index
// Add current string
int sol1 = str_array[start].size() + maxStringSize(str_array, len,
(start + str_array
[start].size() / 2) + 1);
// Remove current string
int sol2 = maxStringSize(str_array, len, start + 1);
// Take max of both
int maxSize = max(sol1, sol2);
// return answer
return maxSize;
}
int main() {
string str_array[] = {"tutor", "po", "nt", "welco", "ghj"};
int len = sizeof(str_array) / sizeof(str_array[0]);
cout << "The maximum size of the resultant string according to given conditions is - " << maxStringSize(str_array, len, 0);
return 0;
}
輸出
The maximum size of the resultant string according to given conditions is - 10
時間複雜度 - O(2^N)，因為我們在遞迴函式中對所有字串都做出了選擇。
空間複雜度 - O(1)，因為我們使用常量空間。
方法 2
此方法將使用記憶化技術來解決問題。它將先前計算的結果儲存在列表中。因此，如果我們需要再次計算相同的操作，我們可以從列表中獲取其值。
演算法
步驟 1 - 定義長度等於陣列長度的“dp”列表，並將其初始化為 -1。
步驟 2 - 如果開始位置大於長度，則返回 0。
步驟 3 - 如果 dp[start] 為 -1，則我們第一次計算該值。
步驟 4 - 執行遞迴函式呼叫。在一個函式呼叫中，包含開始索引處的字串；在一個函式中，不包含開始索引處的字串。
步驟 5 - 將兩個解決方案中的最大值儲存在 dp[start] 中。
步驟 6 - 返回 dp[start] 值。
示例
#include <bits/stdc++.h>
using namespace std;
int maxStringSize(string str_array[], int len, int start, vector<int>
&dp) {
// Return 0 if start exceeds len
if (start >= len)
return 0;
// If value is not calculated for start index
if (dp[start] == -1) {
// Add current string
int sol1 = str_array[start].size() + maxStringSize(str_array, len,
(start + str_array[start].size() / 2) + 1, dp);
// Remove current string
int sol2 = maxStringSize(str_array, len, start + 1, dp);
// Take max of both
dp[start] = max(sol1, sol2);
}
// return answer
return dp[start];
}
int main() {
string str_array[] = {"tutor", "po", "nt", "welco", "ghj"};
int len = sizeof(str_array) / sizeof(str_array[0]);
vector<int> dp(len, -1);
cout << "The maximum size of the resultant string according to given conditions is " << maxStringSize(str_array, len, 0, dp);
return 0;
}
輸出
The maximum size of the resultant string according to given conditions is 10
時間複雜度 - O(N*M)，其中 N 是陣列長度，M 是字串的最大長度。
空間複雜度 - O(N)，因為我們儲存每個開始索引的結果值。
方法 3
在這種方法中，我們將使用動態規劃的表格法來解決問題。它迭代地填充列表，並根據先前狀態確定答案。
演算法
步驟 1 - 定義“matrix”列表。
步驟 2 - 將矩陣的最後一個元素初始化為 0。
步驟 3 - 從最後一個索引開始遍歷陣列。
步驟 4 - 將 sol1 變數初始化為字串大小。如果 p + str_array[p].size() / 2 + 1 小於或等於陣列長度，則從矩陣的 (p + str_array[p].size() / 2 + 1) 索引新增值到 sol1 中。
步驟 5 - 定義“sol2”並將其初始化為 matrix[p+1]。
步驟 6 - 在 matrix[p] 中儲存 sol1 和 sol2 的最大值。
步驟 7 - 返回 matrix[0] 值。
示例
#include <bits/stdc++.h>
using namespace std;
int maxStringSize(string str_array[], int len) {
// List to store results
vector<int> matrix(len + 1);
matrix[len] = 0; // Initialization
// Traverse the string
for (int p = len - 1; p >= 0; p--) {
// Include string at pth index
int sol1 = str_array[p].size();
if (p + str_array[p].size() / 2 + 1 <= len) {
sol1 += matrix[p + str_array[p].size() / 2 + 1];
}
// Don't include string at pth index
int sol2 = matrix[p + 1];
// Answer for last p strings
matrix[p] = max(sol1, sol2);
}
// Return final result
return matrix[0];
}
int main() {
string str_array[] = {"tutor", "po", "nt", "welco", "ghj"};
int len = sizeof(str_array) / sizeof(str_array[0]);
cout << "The maximum size of the resultant string according to given conditions is " << maxStringSize(str_array, len);
return 0;
}
輸出
The maximum size of the resultant string according to given conditions is 10
時間複雜度 - O(N)，因為我們遍歷字串。
空間複雜度 - O(N)，因為我們使用列表來儲存先前結果。
從以上三種方法來看，表格化技術在時間複雜度方面是最好的。記憶化技術是遞迴方法的最佳化版本，因為我們使用了先前計算的結果。
164 次瀏覽
