Dada una string S de longitud 2N y Q Consultas que contienen tres enteros T , A y B cada uno, donde las consultas pueden ser de los siguientes dos tipos:
- T=1: Intercambiar los caracteres Ath y Bth en S. (En indexación basada en 1)
- T=2: Intercambia los primeros N caracteres con los últimos N caracteres, es decir, “ABCD” se convierte en “CDAB”
La tarea es encontrar la string final después de aplicarle las Consultas Q.
Ejemplos:
Entrada: S=”ABCD”, N=2, Q={{2, 0, 0}, {1, 1, 3}, {2, 0, 0}}
Salida:
CBAD
Explicación:
Después de la primera consulta: S= ”CDAB”
Después de la 2.ª consulta: S=”ADCB”
Después de la 3.ª consulta: S=”CBAD”Entrada: S=”GEEK”, N=2, Q={{2, 0, 0}, {1, 1, 2}, {1, 2, 3}, {1, 3, 4}, {2, 0, 0}}
Salida:
EEKG
Enfoque ingenuo: siga los pasos a continuación para resolver el problema:
- Recorra la array Queries y, para cada índice actual i , haga lo siguiente:
- Extraiga T , A y B como T=Q[i][0], A=Q[i][1] y B=Q[i][2].
- Disminuya A y B para convertirlos en 0 indexados.
- Si T es igual a 1 , intercambie los caracteres en el índice A y B respectivamente.
- De lo contrario, recorra la string de 0 a N-1 e intercambie cada A[j] con A[j+N].
- Imprime la string S
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find final string
// after applying all Queries on it
void solve(string S, int N,
vector<vector<int> > Queries,
int Q)
{
// Traverse the Queries array
for (int i = 0; i < Q; i++) {
int T = Queries[i][0], A = Queries[i][1],
B = Queries[i][2];
// convert A, B to zero indexing
A--;
B--;
// Query of 1st type
if (T == 1) {
// swap ath and bth characters
swap(S[A], S[B]);
}
// Query of 2nd type
else {
// swap first N characters
// with last N characters
for (int j = 0; j < N; j++) {
swap(S[j], S[j + N]);
}
}
}
// Print answer
cout << S << endl;
}
// Driver code
int main()
{
// Input
string S = "ABCD";
int N = S.length() / 2;
vector<vector<int> > Queries
= { { 2, 0, 0 }, { 1, 1, 3 }, { 2, 0, 0 } };
int Q = Queries.size();
// Function call
solve(S, N, Queries, Q);
return 0;
}
Python3
# Python3 program for the above approach # Function to find final string # after applying all Queries on it def solve(S, N, Queries, Q): # Traverse the Queries array S = list(S) for i in range(Q): T = Queries[i][0] A = Queries[i][1] B = Queries[i][2] # Convert A, B to zero indexing A -= 1 B -= 1 # Query of 1st type if (T == 1): # Swap ath and bth characters temp = S[A] S[A] = S[B] S[B] = temp # Query of 2nd type else: # Swap first N characters # with last N characters for j in range(N): temp = S[j] S[j] = S[j + N] S[j + N] = temp S = ''.join(S) # Print answer print(S) # Driver code if __name__ == '__main__': # Input S = "ABCD" N = len(S) // 2 Queries = [ [ 2, 0, 0 ], [ 1, 1, 3 ], [ 2, 0, 0 ] ] Q = len(Queries) # Function call solve(S, N, Queries, Q) # This code is contributed by ipg2016107
CBAD
Complejidad temporal: O(N*Q)
Espacio auxiliar: O(1)
Enfoque eficiente: no es necesario intercambiar los primeros N caracteres con los últimos N caracteres para cada consulta de tipo 2. Esto se puede hacer una vez al final haciendo un seguimiento de cuántas veces se hace en una variable separada. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable flip a 0 , que realiza un seguimiento de cuántas veces se realiza una consulta de tipo 2 en S .
- Recorra la array Queries y, para cada índice actual i , haga lo siguiente:
- Extraiga T , A y B como T=Q[i][0], A=Q[i][1] y B=Q[i][2].
- Disminuya A y B para convertirlos en 0 indexados.
- Si T es igual a 1 , haga lo siguiente:
- Compruebe si el volteo es parejo. Si es así, simplemente intercambie los caracteres Ath y Bth en S
- De lo contrario, actualice los valores de A y B en consecuencia (a medida que se invierte la string) agregando N a ellos y luego, tomando su módulo con 2N . Luego intercambie los caracteres Ath y Bth en S .
- De lo contrario, incrementa el giro
- Compruebe si el volteo es parejo. Si es así, imprima S tal como es.
- De lo contrario, S se invierte, así que imprima los últimos N caracteres de S primero y luego, los primeros N caracteres de S .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find final string
// after applying all Queries on it
void solve(string S, int N,
vector<vector<int> > Queries,
int Q)
{
int flip = 0;
// Traverse the Queries array
for (int i = 0; i < Q; i++) {
int T = Queries[i][0], A = Queries[i][1],
B = Queries[i][2];
// convert A, B to zero indexing
A--;
B--;
// Query of 1st type
if (T == 1) {
// simply swap the character at
// Ath and Bth index
if (flip % 2 == 0)
swap(S[A], S[B]);
else {
// add N to A, B as string starts at nth
// index(0 indexing) and take mod with size
// of string (2*N) and swap the character at
// Ath and Bth index calculated.
A = (A + N) % (2 * N);
B = (B + N) % (2 * N);
swap(S[A], S[B]);
}
}
// Query of 2nd type
else {
// increment flip
flip++;
}
}
// Print answer
if (flip % 2 == 0)
cout << S << endl;
else {
// string starts at Nth index;
for (int i = N; i < 2 * N; i++)
cout << S[i];
for (int i = 0; i < N; i++)
cout << S[i];
cout << endl;
}
}
// Driver code
int main()
{
// Input
string S = "ABCD";
int N = S.length() / 2;
vector<vector<int> > Queries
= { { 2, 0, 0 }, { 1, 1, 3 }, { 2, 0, 0 } };
int Q = Queries.size();
// Function call
solve(S, N, Queries, Q);
return 0;
}
CBAD
Complejidad temporal: O(N+Q)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por _bipulsingh y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA