数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究通过交换给定字符或水平旋转来翻转字符串，进行 Q 次查询
通过交换给定字符或水平旋转来翻转字符串，进行 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".
解释
应用第一个查询（类型 2）得到字符串“CDAB”。
执行第二个查询（类型 1）交换位置 1 和 3 的字符，将字符串转换为“ADCB”。
第三个查询（类型 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".
解释
应用第一个查询（类型 2）不会修改字符串：“LEAP”。
执行第二个查询（类型 1）交换位置 1 和 2 的字符，得到“ELAP”。
第三个查询（类型 1）交换位置 2 和 3 的字符，转换为“EALP”。
执行第四个查询（类型 1）交换位置 3 和 4 的字符，得到“EAPL”。
最终查询（类型 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 <stdio.h>
#include <stdlib.h> // Add this line to include stdlib.h
#include <string.h>
// Function to swap characters at indices a and b in a string
void swapCharacters(char *str, int a, int b) {
char temp = str[a - 1];
str[a - 1] = str[b - 1];
str[b - 1] = temp;
}
// Function to rotate a string by N positions
void rotateString(char *str, int N) {
int length = strlen(str);
if (N <= 0 || N >= length)
return;
char temp[N];
strncpy(temp, str, N);
memmove(str, str + N, length - N);
strncpy(str + length - N, temp, N);
}
// Function to apply queries to a string
char* applyQueries(const char* str, int N, int queries[][3], int numQueries) {
char* modifiedString = strdup(str);
for (int i = 0; i < numQueries; i++) {
int type = queries[i][0];
int a = queries[i][1];
int b = queries[i][2];
if (type == 1) {
swapCharacters(modifiedString, a, b);
} else {
rotateString(modifiedString, N);
}
}
return modifiedString;
}
int main() {
char S[] = "ABCD";
int N = 2;
int queries[][3] = {{2, 0, 0}, {1, 1, 3}, {2, 0, 0}};
int numQueries = sizeof(queries) / sizeof(queries[0]);
char* result = applyQueries(S, N, queries, numQueries);
printf("Final String: %s\n", result);
free(result); // Now free can be used without warnings
return 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
import java.util.ArrayList;
import java.util.List;
public class StringManipulation {
// Function to swap characters at indices a and b in a string
public static String swapCharacters(String str, int a, int b) {
char[] charArray = str.toCharArray();
char temp = charArray[a - 1];
charArray[a - 1] = charArray[b - 1];
charArray[b - 1] = temp;
return new String(charArray);
}
// Function to rotate a string by N positions
public static String rotateString(String str, int N) {
int length = str.length();
if (N <= 0 || N >= length)
return str;
String temp = str.substring(0, N);
return str.substring(N) + temp;
}
// Function to apply queries to a string
public static String applyQueries(String str, int N, List<int[]> queries) {
String modifiedString = str;
for (int[] query : queries) {
int type = query[0];
int a = query[1];
int b = query[2];
if (type == 1) {
modifiedString = swapCharacters(modifiedString, a, b);
} else {
modifiedString = rotateString(modifiedString, N);
}
}
return modifiedString;
}
public static void main(String[] args) {
String S = "ABCD";
int N = 2;
List<int[]> queries = new ArrayList<>();
queries.add(new int[]{2, 0, 0});
queries.add(new int[]{1, 1, 3});
queries.add(new int[]{2, 0, 0});
String result = applyQueries(S, N, queries);
System.out.println("Final String: " + result);
}
}
输出
Final String: CBAD
def swap_characters(s, a, b):
s_list = list(s)
s_list[a - 1], s_list[b - 1] = s_list[b - 1], s_list[a - 1]
return ''.join(s_list)
def rotate_string(s, N):
if N <= 0 or N >= len(s):
return s
return s[N:] + s[:N]
def apply_queries(s, N, queries):
modified_string = s
for query in queries:
type, a, b = query
if type == 1:
modified_string = swap_characters(modified_string, a, b)
else:
modified_string = rotate_string(modified_string, N)
return modified_string
S = "ABCD"
N = 2
queries = [[2, 0, 0], [1, 1, 3], [2, 0, 0]]
result = apply_queries(S, N, queries)
print("Final String:", result)
输出
Final String: CBAD
结论
总而言之，通过交换给定字符或水平旋转来翻转字符串以进行 Q 次查询的问题，为字符串操作提供了一个有趣的练习。在本教程中，我们探讨了问题陈述，讨论了它在各种编程语言中的实现，并提供了逐步解决方案。通过利用 C、C++、Java 和 Python 编程技术以及使用函数来交换字符和旋转字符串，我们成功地解决了问题并获得了所需的输出。通过本教程，读者可以有效地解决类似的问题或挑战。快乐学习！快乐编码！
86 次浏览
