C++ 通过交换给定字符或水平旋转字符串来翻转字符串，有Q个查询

将字符串通过交换给定的字符或水平旋转字符串来翻转，这是一个非常有趣的问题，涉及到基于一系列查询操作的字符串操作。在这个教程中，我们将深入研究这个问题，并使用C++提供一个解决方案。

问题的陈述围绕着一个字符字符串和一组查询，每个查询包含指令来交换特定的字符或执行水平旋转。我们的目标是在应用所有查询之后确定字符串的最终配置。

通过本教程，我们将探索问题的复杂性，讨论C++的实现细节，并提供一个逐步指南来高效解决问题。最后，读者将全面了解如何使用C++编程解决类似的字符串操作挑战。因此，让我们进入令人兴奋的翻转字符串的世界，发现等待我们的优雅解决方案。

问题陈述

考虑一个长度为2N的字符串和由三个整数T、A和B表示的一组查询。每个查询类型T可以是1或2。对于类型1的查询，在字符串中第A个和B个字符（使用从1开始的索引）交换，而对于类型2的查询，将首个N个字符与最后N个字符交换。目标是找出应用所有查询后的结果字符串。

让我们通过例子来理解这个问题陈述。

示例1

输入

Given a string "ABCD" with N = 2 and the following queries: {{2, 0, 0}, {1, 1, 3}, {2, 0, 0}}

输出

The final string is "CBAD".

解释

1. 应用第一个查询（类型2），结果为字符串“CDAB”。

2. 进行第二个查询（类型1），交换位置1和3上的字符，将字符串转换为“ADCB”。

3. 第三个查询（类型2）将前N个字符与后N个字符交换，得到最终字符串“CBAD”。

示例2

输入

Consider the string "LEAP" with N = 2 and the queries: {{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

结论

总之，通过交换给定的字符或者水平旋转字符串来翻转一个字符串的问题对于字符串操作提供了一个有趣的练习。在本教程中，我们探讨了问题陈述，讨论了其在C++中的实现，并提供了一步一步的解决方案。通过利用C++编程技巧和利用函数来交换字符和旋转字符串，我们成功地解决了问题并获得了所需的输出。通过这个教程，读者可以高效地解决类似的问题或挑战。愿您学习愉快，编码愉快！