資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究給定字元替換最多 K 個字元後的最長子字串（針對 Q 個查詢）
在這個問題中，我們給定 M 個查詢，並且在對給定字串執行每個查詢後，我們需要列印只包含字元“ch”的字串的最大長度。
我們將使用動態規劃的表格法來找到替換最多 K 個字元為給定字元後子字串的最大可能長度。
問題陳述 - 我們給定一個長度為 N 的字串 alpha 和一個包含 M 個查詢的陣列 que[]，查詢型別為 {K, ch}，其中 K 是一個正整數，ch 是一個字元。給定對於每個查詢，我們可以用字元“ch”替換最多 K 個字元。給定的任務是列印僅包含“ch”字元的子字串的最大長度。
示例
輸入
alpha = "tutorials"; que = {{1, 't'}, {2, 't'}, {3, 'o'}};
輸出
3 4 4
解釋
執行第一個查詢後，字串變為“tttorials”。所以，字串包含一個包含 3 個“t”字元的子字串。
執行第二個查詢後，字串變為“ttttrials”。所以，我們可以取“tttt”子字串。
在第三個查詢中，字串變為“oooorials”。所以，我們可以取“oooo”子字串。
輸入
alpha = "nayan"; que = {{1, 'n'}, {2, 'n'}, {3, 'n'}};
輸出
2 3 5
解釋 -
如果我們將一個字元替換為“n”，我們得到“nn”作為子字串。
如果我們將兩個字元替換為“n”，我們得到“nnn”子字串。
執行第三個查詢後，字串變為“nnnnn”，我們可以將整個字串作為子字串。
方法 1
在這種方法中，我們將遍歷每個查詢並在給定字串上執行每個查詢。我們將定義一個函式使用動態規劃方法來處理查詢。在動態規劃技術中，我們可以透過包含或排除子字串中的特定字元來找到子字串的最大長度。
演算法
步驟 1 - 執行 processQueries() 函式來處理查詢。
步驟 1.1 - 在 processQueries() 函式中，用 0 初始化“matrix”陣列。
步驟 1.2 - 接下來，將 matrix[p][0][alpha[p - 1] - 'a'] 初始化為 1，因為我們可以將特定字元作為子字串。這裡，p 表示子字串長度，q 表示字元索引，“r”表示字元索引。
步驟 1.3 - 從 1 到 len 索引開始遍歷矩陣。此外，使用巢狀迴圈從 0 遍歷到 p，另一個巢狀迴圈遍歷所有字母字元。
步驟 1.4 - 如果索引 p - 1 處的字元與字元 r 相同，則將 matrix[p][q][r] 更新為 matrix[p - 1][q][r] + 1。我們在此步驟中包含當前字元。
步驟 1.5 - 否則，將 matrix[p][q][r] 更新為 matrix[p - 1][q - 1][r] + 1。我們在此步驟中排除當前字元。
步驟 1.6 - 現在，用 0 填充 process[] 陣列。
步驟 1.7 - 遍歷矩陣，並將 process[p][q] 填充為 max(process[p][q], matrix[r][p][q])。這裡，對於每個索引，我們儲存最大值。
步驟 2 - 定義“answer”列表來儲存所有查詢的答案。
步驟 3 - 遍歷所有查詢並獲取每個查詢的輸出。
步驟 4 - 根據查詢的正整數和字元從 process[] 陣列中獲取輸出值，並將結果推入“answer”列表。
步驟 5 - 返回“answer”列表。
示例
#include <bits/stdc++.h>
using namespace std;
int matrix[1001][1001][26];
int process[1001][26];
void processQueries(string alpha) {
int len = alpha.length();
// Fill array with 0
memset(matrix, 0, sizeof(matrix));
for (int p = 1; p <= len; p++) {
// Length of substring is 1 for characters of substring
matrix[p][0][alpha[p - 1] - 'a'] = 1;
}
for (int p = 1; p <= len; p++) {
for (int q = 0; q <= p; q++) {
for (int r = 0; r < 26; r++) {
// When character at index p is equal to r + 'a', add 1 to the result of previous index
if (alpha[p - 1] == char(r + 'a')) {
matrix[p][q][r] = matrix[p - 1][q][r] + 1;
} else if (q != 0) {
// Q == 0 is already calculated. So, we update only when q != 0
matrix[p][q][r] = matrix[p - 1][q - 1][r] + 1;
}
}
}
}
// Fill the process[] array with 0.
memset(process, 0, sizeof(process));
for (int p = 1; p <= len; p++) {
for (int q = 0; q < 26; q++) {
for (int r = 1; r <= len; r++) // Get maximum length
process[p][q] = max(process[p][q], matrix[r][p][q]);
}
}
}
vector<int> performOperations(string alpha, vector<pair<int, char>> &que) {
processQueries(alpha);
vector<int> answer;
// Find answers from process[] array
for (auto pair : que) {
answer.push_back(process[pair.first][pair.second - 'a']);
}
return answer;
}
int main() {
string alpha = "tutorials";
vector<pair<int, char>> que = {{1, 't'}, {2, 't'}, {3, 'o'}};
vector<int> answer = performOperations(alpha, que);
cout << "The length of longest substrings after performing the queries are : \n";
for (int num : answer)
cout << num << " ";
return 0;
}
輸出
The length of longest substrings after performing the queries are : 3 4 4
時間複雜度 - O(N*N + M)，其中 O(N*N) 用於處理查詢，O(M) 用於遍歷查詢。
空間複雜度 - O(M) 用於儲存所有查詢的答案。
在解決方案中，我們首先處理了查詢，然後我們找到每個查詢的答案，這提高了程式碼的時間複雜度。否則，我們需要分別處理所有查詢。
147 次瀏覽
