通过交换给定字符或水平旋转 Q 查询来翻转字符串
通过交换给定字符或水平旋转 Q 查询来翻转字符串是一个有趣的问题，它涉及根据一系列查询来操作字符串。在本教程中，我们将深入研究这个问题并使用 C++ 提供解决方案。
问题陈述围绕一个字符串和一组查询展开，每个查询都包含交换特定字符或执行水平旋转的指令。我们的目标是在应用所有查询后确定字符串的最终配置。
通过本教程，我们将探索问题的复杂性，讨论 C++ 中的实现细节，并提供有效解决问题的分步指南。最后，读者将全面了解如何使用 C++ 编程解决类似的字符串操作挑战。那么，让我们深入翻转字符串的激动人心的世界，发现等待我们的优雅解决方案。
问题陈述
考虑一个长度为 2N 的字符串和一组由三个整数 T、A 和 B 表示的查询。每个查询类型 T 可以是 1 或 2。对于类型 1 查询，字符串中的第 A 个和第 B 个字符(使用基于 1 的索引)被交换，而对于类型 2 查询，前 N 个字符与后 N 个字符交换。目标是在应用所有查询后找到结果字符串。
让我们通过示例来理解这个问题陈述。
示例 1
输入
给定一个字符串"ABCD"，N = 2，以及以下查询:{{2, 0, 0}, {1, 1, 3}, {2, 0, 0}}
输出
最终字符串为"CBAD"。
解释
1. 应用第一个查询(类型 2)得到字符串"CDAB"。
2.执行第二个查询(类型 1)会交换位置 1 和 3 处的字符，从而将字符串转换为"ADCB"。
3. 第三个查询(类型 2)会交换前 N 个字符与后 N 个字符，从而得到最终字符串"CBAD"。
示例 2
输入
考虑 N = 2 的字符串"LEAP"和查询:{{2, 0, 0}, {1, 1, 2}, {1, 2, 3}, {1, 3, 4}, {2, 0, 0}}
输出
The final string is "EAPL".
解释
1. 应用第一个查询(类型 2)不会修改字符串:"LEAP"。
2. 执行第二个查询(类型 1)会交换位置 1 和 2 处的字符，结果为"ELAP"。
3. 第三个查询(类型 1)会交换位置 2 和 3 处的字符，将字符串转换为"EALP"。
4. 执行第四个查询(类型 1)会交换位置 3 和 4 处的字符，结果为"EAPL"。
5.最后一个查询(类型 2)将前 N 个字符与后 N 个字符交换，使字符串保持不变:"EAPL"。
因此，在将所有查询应用于输入字符串"LEAP"后，最终字符串为"EAPL"。
算法
步骤 1. 定义函数"swapCharacters"，根据给定字符串中的两个字符的索引交换它们。
步骤 2. 定义函数"rotateString"，通过将前"N"个字符移动到字符串末尾，将给定字符串旋转"N"个位置。
步骤 3. 定义函数"applyQueries"，以原始字符串、旋转值"N"和查询向量作为输入。
步骤 4. 将"modifiedString"初始化为原始字符串的副本。
步骤 5. 遍历向量中的每个查询查询。
从当前查询中提取类型、"a"和"b"值。
如果类型为 1，则调用"swapCharacters"在"modifiedString"中交换索引"a"和"b"处的字符。
否则，调用"rotateString"将"modifiedString"旋转"N"个位置。
步骤 6. 返回修改后的字符串。
步骤 7. 在"main"函数中，初始化原始字符串"S"、旋转值"N"和查询向量。
步骤 8. 使用这些值调用"applyQueries"函数以获取修改后的字符串。
步骤 9. 将最终字符串打印为输出。
示例
使用 C++ 实现上述算法
下面的 C++ 程序获取字符串"S"，并根据一组查询对其执行不同的操作。查询表示为向量的向量，其中每个内部向量包含三个元素:操作类型，以及表示要交换字符的索引"a"和"b"。程序将这些查询应用于字符串"S"，并生成修改后的字符串作为输出。
输入
"ABCD"; N: 2; Queries: {{2, 0, 0}, {1, 1, 3}, {2, 0, 0}};
输出
Final String: "CBAD"
示例
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
void swapCharacters(std::string& str, int a, int b) {
std::swap(str[a - 1], str[b - 1]);
}
void rotateString(std::string& str, int N) {
int length = str.length();
if (N <= 0 || N >= length)
return;
std::string temp = str.substr(0, N);
str.erase(0, N);
str += temp;
}
std::string applyQueries(const std::string& str, int N, const
std::vector<std::vector<int>>& queries) {
std::string modifiedString = str;
for (const std::vector<int>& query : queries) {
int type = query[0];
int a = query[1];
int b = query[2];
if (type == 1) {
swapCharacters(modifiedString, a, b);
} else {
rotateString(modifiedString, N);
}
}
return modifiedString;
}
int main() {
std::string S = "ABCD";
int N = 2;
std::vector<std::vector<int>> queries = {{2, 0, 0}, {1, 1, 3}, {2, 0, 0}};
std::string result = applyQueries(S, N, queries);
std::cout << "Final String: " << result << std::endl;
return 0;
}
输出
Final String: CBAD
结论
总之，通过交换给定字符或水平旋转字符串来翻转 Q 查询的问题为字符串操作提供了一个有趣的练习。在本教程中，我们探讨了问题陈述，讨论了它在 C++ 中的实现，并提供了分步解决方案。通过利用 C++ 编程技术并利用函数交换字符和旋转字符串，我们成功解决了该问题并获得了所需的输出。通过本教程，读者可以有效地解决类似的问题或挑战。祝您学习愉快。编码愉快!
