Dada una string str , la tarea es realizar el siguiente tipo de consultas en la string dada:
- (1, K): gira la string a la izquierda K caracteres.
- (2, K): imprime el carácter K de la string.
Ejemplos:
Entrada: str = “abcdefgh”, q[][] = {{1, 2}, {2, 2}, {1, 4}, {2, 7}}
Salida:
d
e
Consulta 1: str = “cdefghab ”
Consulta 2: el 2º carácter es d
Consulta 3: str = “ghabcdef”
Consulta 4: el 7º carácter es e
Entrada: str = “abc”, q[][] = {{1, 2}, {2, 2 }}
Salida:
un
Enfoque: la observación principal aquí es que no es necesario rotar la string en cada consulta; en su lugar, podemos crear un puntero ptr que apunte al primer carácter de la string y que se pueda actualizar para cada rotación como ptr = (ptr + K ) % N donde K es el número entero por el cual se debe rotar la string y N es la longitud de la string. Ahora, para cada consulta del segundo tipo, el carácter K se puede encontrar mediante str[( ptr + K – 1) % N] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define size 2
// Function to perform the required
// queries on the given string
void performQueries(string str, int n,
int queries[][size], int q)
{
// Pointer pointing to the current starting
// character of the string
int ptr = 0;
// For every query
for (int i = 0; i < q; i++) {
// If the query is to rotate the string
if (queries[i][0] == 1) {
// Update the pointer pointing to the
// starting character of the string
ptr = (ptr + queries[i][1]) % n;
}
else {
int k = queries[i][1];
// Index of the kth character in the
// current rotation of the string
int index = (ptr + k - 1) % n;
// Print the kth character
cout << str[index] << " ";
}
}
}
// Driver code
int main()
{
string str = "abcdefgh";
int n = str.length();
int queries[][size] = { { 1, 2 }, { 2, 2 },
{ 1, 4 }, { 2, 7 } };
int q = sizeof(queries) / sizeof(queries[0]);
performQueries(str, n, queries, q);
return 0;
}
d e
Complejidad temporal: O(Q), donde Q es el número de consultas.
Espacio Auxiliar: O(1)
¡ Consulte el artículo completo sobre Consultas de rotación y K-ésimo carácter de la string dada en tiempo constante para obtener más detalles!
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA