資料結構
網路
關係資料庫管理系統 (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 次瀏覽
