Рубрики

Запросы на вращение и K-й символ данной строки в постоянном времени

Для заданной строки str задача состоит в том, чтобы выполнить следующий тип запросов для данной строки:

  1. (1, K): поверните строку влево на K символов.
  2. (2, K): печать K- го символа строки.

Примеры:

Input: str = “abcdefgh”, q[][] = {{1, 2}, {2, 2}, {1, 4}, {2, 7}}
Output:
d
e
Query 1: str = “cdefghab”
Query 2: 2nd character is d
Query 3: str = “ghabcdef”
Query 4: 7th character is e

Input: str = “abc”, q[][] = {{1, 2}, {2, 2}}
Output:
a

Подход: основное наблюдение здесь заключается в том, что строку не нужно вращать в каждом запросе, вместо этого мы можем создать указатель ptr, указывающий на первый символ строки и который можно обновлять для каждого поворота как ptr = (ptr + K )% N где K целое число, на которое необходимо повернуть строку, а N — длина строки. Теперь для каждого запроса второго типа K- й символ может быть найден с помощью str [(ptr + K — 1)% N] .

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

  
#define size 2

  
// Функция для выполнения требуемого
// запросы по заданной строке

void performQueries(string str, int n,

                    int queries[][size], int q)

{

  

    // Указатель, указывающий на текущий старт

    // символ строки

    int ptr = 0;

  

    // Для каждого запроса

    for (int i = 0; i < q; i++) {

  

        // Если запрос вращать строку

        if (queries[i][0] == 1) {

  

            // Обновляем указатель, указывающий на

            // начальный символ строки

            ptr = (ptr + queries[i][1]) % n;

        }

        else {

  

            int k = queries[i][1];

  

            // Индекс k-го символа в

            // текущее вращение строки

            int index = (ptr + k - 1) % n;

  

            // Распечатать kth символ

            cout << str[index] << "\n";

        }

    }

}

  
// Код драйвера

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;

}

Джава

// Java реализация вышеуказанного подхода

import java.util.*;

class GFG 

{

static int size = 2;

  
// Функция для выполнения требуемого
// запросы по заданной строке

static void performQueries(String str, int n,

                           int queries[][], int q)

{

  

    // Указатель, указывающий на текущий

    // начальный символ строки

    int ptr = 0;

  

    // Для каждого запроса

    for (int i = 0; i < q; i++) 

    {

  

        // Если запрос вращать строку

        if (queries[i][0] == 1)

        {

  

            // Обновляем указатель, указывающий на

            // начальный символ строки

            ptr = (ptr + queries[i][1]) % n;

        }

        else 

        {

            int k = queries[i][1];

  

            // Индекс k-го символа в

            // текущее вращение строки

            int index = (ptr + k - 1) % n;

  

            // Распечатать kth символ

            System.out.println(str.charAt(index));

        }

    }

}

  
// Код драйвера

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);

}

  
// Этот код предоставлен 29AjayKumar

python3

# Python3 реализация подхода

size = 2

  
# Функция для выполнения требуемого
# запросов по заданной строке

def performQueries(string, n, queries, q) : 

  

    # Указатель, указывающий на текущий старт

    # символ строки

    ptr = 0

  

    # Для каждого запроса

    for i in range(q) :

  

        # Если запрос вращать строку

        if (queries[i][0] == 1) : 

  

            # Обновить указатель, указывающий на

            # начальный символ строки

            ptr = (ptr + queries[i][1]) % n; 

              

        else :

  

            k = queries[i][1]; 

  

            # Индекс k-го символа в

            # текущее вращение строки

            index = (ptr + k - 1) % n; 

  

            # Распечатать kth символ

            print(string[index]); 

  
# Код драйвера

if __name__ == "__main__"

  

    string = "abcdefgh"

    n = len(string); 

  

    queries = [[ 1, 2 ], [ 2, 2 ], 

               [ 1, 4 ], [ 2, 7 ]]; 

    q = len(queries); 

  

    performQueries(string, n, queries, q); 

      
# Этот код предоставлен AnkitRai01

C #

// C # реализация подхода

using System;

      

class GFG 

{

static int size = 2;

  
// Функция для выполнения требуемого
// запросы по заданной строке

static void performQueries(String str, int n,

                           int [,]queries, int q)

{

  

    // Указатель, указывающий на текущий

    // начальный символ строки

    int ptr = 0;

  

    // Для каждого запроса

    for (int i = 0; i < q; i++) 

    {

  

        // Если запрос вращать строку

        if (queries[i, 0] == 1)

        {

  

            // Обновляем указатель, указывающий на

            // начальный символ строки

            ptr = (ptr + queries[i, 1]) % n;

        }

        else

        {

            int k = queries[i, 1];

  

            // Индекс k-го символа в

            // текущее вращение строки

            int index = (ptr + k - 1) % n;

  

            // Распечатать kth символ

            Console.WriteLine(str[index]);

        }

    }

}

  
// Код драйвера

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.GetLength(0);

  

    performQueries(str, n, queries, q);

}
}

  
// Этот код предоставлен PrinciRaj1992

Выход:

d
e

Рекомендуемые посты:

Запросы на вращение и K-й символ данной строки в постоянном времени

0.00 (0%) 0 votes