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:
Java
// Java implementation of the above approach
import java.util.*;
class GFG
{
static int size = 2;
// Function to perform the required
// queries on the given string
static void performQueries(String str, int n,
int queries[][], 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
System.out.println(str.charAt(index));
}
}
}
// Driver code
public static void main(String[] args)
{
String str = "abcdefgh";
int n = str.length();
int queries[][] = { { 1, 2 }, { 2, 2 },
{ 1, 4 }, { 2, 7 } };
int q = queries.length;
performQueries(str, n, queries, q);
}
}
// This code is contributed by 29AjayKumar
d e
Complejidad de tiempo: 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