数据结构
网络
关系数据库管理系统
操作系统
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 次浏览
