C++程序 在常数时间内查询给定字符串的旋转和第K个字符

C++程序 在常数时间内查询给定字符串的旋转和第K个字符

给定一个字符串 str ,任务是在给定字符串上执行以下类型的查询:

  1. (1, K): 将字符串左旋转 K 个字符。
  2. (2, K): 打印字符串的 **第K个 th ** 字符。

示例:

输入: str = “abcdefgh”, q[][] = {{1, 2}, {2, 2}, {1, 4}, {2, 7}}

输出:

d

e

查询1: str = “cdefghab”

查询2: 第2个字符是d

查询3: str = “ghabcdef”

查询4: 第7个字符是e

输入: str = “abc”, q[][] = {{1, 2}, {2, 2}}

输出:

a

方法: 这里的主要观察是,在每个查询中字符串不需要被旋转,而是可以创建一个指向字符串第一个字符的指针 ptr ,可用于每次旋转更新为: ptr = (ptr+K)%N 这里 K 是需要旋转字符串的整数, N 是字符串的长度。 现在,对于每个第二类型的查询,可以通过 str [(ptr + K-1)%N] 找到第 K th字符。

下面是以上方法的实现:

// 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 

时间复杂度: O(Q), 其中Q是查询数量。

辅助空间: O(1)

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程

C++ 示例