数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究针对 M 个查询，反转给定字符串的范围
在这个问题中，我们将根据数组值对给定的字符串执行 M 次反转查询。
解决该问题的朴素方法是根据给定的数组值反转每个字符串片段。
优化方法利用了以下逻辑：当我们对同一个子字符串反转两次时，我们会得到原始字符串。
问题陈述 - 我们给定一个包含字母字符的 alpha 字符串。此外，我们还给定一个大小为 M 的 arr[] 数组，其中包含正整数。我们需要对给定的字符串执行 M 个操作并返回最终字符串。
在每个操作中，我们需要获取 arr[i] 并反转从 arr[i] 到 N − arr[i] + 1 的子字符串。
示例
输入
alpha = "pqrst"; arr = {2, 1};
输出
tqrsp
解释
执行第一个查询后，字符串变为“psrqt”。
执行第二个查询后，我们得到“tqrsp”。
输入
− alpha = "pqrst"; arr = {1, 1};
输出
− ‘pqrst’
解释 - 如果我们对同一个查询执行偶数次，我们会得到相同的字符串。
输入
− alpha = "pqrst"; arr = {1, 1, 1};
输出
− ‘tsrqp’
解释 - 如果我们对同一个查询执行奇数次，我们会得到字符串的反转。
方法 1
在这种方法中，我们将使用 reverse() 方法反转子字符串。我们将使用给定的查询获取起始和结束指针，并反转给定字符串的子字符串。
算法
步骤 1 - 开始遍历查询数组。
步骤 2 - 使用 arr[p] − 1 初始化“left”变量。
步骤 3 - 使用 str_len − arr[p] + 1 初始化“right”变量。
步骤 4 - 使用 reverse() 方法反转从左指针到右指针的子字符串。
示例
#include <bits/stdc++.h>
using namespace std;
void reverseStrings(string &alpha, int str_len, vector<int> &arr, int arr_len){
// Traverse all queries
for (int p = 0; p < arr_len; p++){
// Get starting pointer
int left = arr[p] - 1;
// Ending pointer
int right = str_len - arr[p] + 1;
// Reverse the string
reverse(alpha.begin() + left, alpha.begin() + right);
}
}
int main(){
int str_len = 5;
string alpha = "pqrst";
int arr_len = 2;
vector<int> arr = {2, 1};
reverseStrings(alpha, str_len, arr, arr_len);
cout << "The string after performing queries is " << alpha << endl;
return 0;
}
输出
The string after performing queries is tqrsp
时间复杂度 - 反转子字符串 M 次的时间复杂度为 O(N*M)。
空间复杂度 - O(1)，因为我们没有使用任何动态空间。
方法 2
在这种方法中，我们将计算特定索引以及在给定查询中包含反转的次数。如果任何索引在偶数次包含在反转中，我们不需要反转它。如果任何索引在所有给定查询中奇数次包含在反转中，我们需要反转特定索引处的字符。
算法
步骤 1 - 初始化长度等于字符串长度的“cnt”列表，并将其值初始化为 0，以存储特定索引包含在反转中的次数。
步骤 2 - 遍历给定查询的数组，并根据当前查询获取字符串的左指针和右指针。
步骤 3 - 还执行 changeRange() 函数以根据当前查询的左指针和右指针更新“cnt”列表。
步骤 3.1 - 在 changeRange() 函数中，增加“cnt”列表中“left”索引处的值。
步骤 3.2 - 减小“cnt”列表中所有位于“right + 1”指针右侧的值。
这里，我们需要在 [left, right] 范围内将“cnt”列表的所有值加 1。因此，我们只将 cnt[left] 加 1，因为获取前缀和会将所有位于“left”索引右侧的值加 1。此外，我们不希望增加 [right, str_len] 索引之间的 cnt 值，因此我们已经将其减 1，因为前缀和会将其加 1。
步骤 4 - 接下来，执行 getPrefixSum() 函数以计算“cnt”列表的前缀和。
步骤 4.1 - 在 getPrefixSum() 函数中，遍历字符串并将前一个元素的值添加到当前元素。
步骤 5 - 接下来，以相反的顺序遍历“cnt”列表。如果当前元素为奇数，则将其追加到“tmp”字符串。
步骤 6 - 使用 0 初始化“p”和“q”，以原始顺序遍历“cnt”列表。
步骤 7 - 如果“cnt”列表中的当前元素为奇数，则使用 tmp[q] 更新 alpha[p]。
步骤 8 - 最后，返回 alpha 字符串。
示例
#include <iostream>
#include <vector>
using namespace std;
void changeRange(vector<int>& cnt, int left, int right) {
// Increase the value of the left index
cnt[left]++;
// Decrement value for all indexes after the right index
if (right + 1 < cnt.size())
cnt[right + 1]--;
}
void getPrefixSum(vector<int>& cnt) {
// Calculate prefix sum
for (int p = 1; p < cnt.size(); p++) {
cnt[p] += cnt[p - 1];
}
}
string reverseStrings(string alpha, int str_len, vector<int>& arr, int arr_len) {
vector<int> cnt(str_len, 0);
// Traverse the array
for (int p = 0; p < arr_len; p++) {
int left = arr[p] <= (str_len + 1) / 2 ? arr[p] - 1 : str_len - arr[p];
int right = arr[p] <= (str_len + 1) / 2 ? str_len - arr[p] : arr[p] - 1;
// Changes index ranges between left and right
changeRange(cnt, left, right);
}
getPrefixSum(cnt);
string tmp;
// Store characters with the odd reversal in the reverse order in the tmp string
for (int p = cnt.size() - 1; p >= 0; p--) {
if (cnt[p] % 2 != 0)
tmp.push_back(alpha[p]);
}
int p = 0, q = 0;
// For even reversal, pick the character from the original string.
// For odd reversal, pick the character from the temp string.
for (p = 0; p < cnt.size(); p++) {
if (cnt[p] % 2 != 0)
alpha[p] = tmp[q++];
}
// Answer string
return alpha;
}
int main() {
int str_len = 5;
string alpha = "pqrst";
int arr_len = 2;
vector<int> arr = { 2, 1 };
alpha = reverseStrings(alpha, str_len, arr, arr_len);
cout << "The string after performing queries is: " <<alpha << endl;
return 0;
}
输出
The string after performing queries is: tqrsp
时间复杂度 - O(M*N + N)，其中 O(M*N) 用于根据查询更新“cnt”列表，O(N) 用于更新给定字符串。
空间复杂度 - O(N)，用于使用“cnt”列表。
在第一种方法中，我们使用 reveres() 方法对给定字符串执行所有查询。在第二种方法中，我们使用前缀和技术来计算特定索引包含在反转中的次数。
235 次查看
