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

---

在这个问题中，程序员需要对字符串执行查询。此外，还需要旋转字符串并打印更新后的字符串的字符。解决此问题的最佳方法是不断更新索引值，并在需要打印字符时访问字符串字符。

问题陈述 – 我们给定字符串 alpha 和包含名为 'que' 的数字对的数组。任务是在字符串 alpha 上执行数组中给出的查询。

遵循以下查询操作规则。

• (1, a) – 对给定字符串进行总共左旋转。

• (2, a) – 打印第 a 个位置的字符。

注意 – 这里，a 的值是 1 到 N，其中 N 是字符串的长度。

示例

输入

que[][] = { { 1, 1 }, { 2, 1 }, { 2, 5 }, { 1, 3 } }, alpha = "wqedsdcs";

输出

q, d

解释 – 让我们逐一在字符串上执行所有查询。

• 第一个查询将字符串旋转 1 位，更新后的字符串将为 'qedsdcsw'。

• 第二个查询打印第 1 个位置的字符，即 'q'。

• 第三个查询打印第 5 个位置的字符，即 'd'。

• 第四个查询进行 3 次左旋转。

输入

que[][] = { { 1, 1 }, { 2, 3 }, { 1, 8 }, { 2, 7 } }, alpha = "tutorialspoint"

输出

o, u

解释

• 执行第一个查询后，字符串变为 'utorialspoint'。

• 更新后的字符串中第 3 个位置的字符是 'o'。

• 执行第三个查询后，字符串变为 'pointtutorials'。

• 第 7 个位置的字符是 'u'。

方法 1

在这种方法中，我们定义索引指针来跟踪当前索引。我们跟踪最后一个索引以在最后一个索引上执行下一个查询。

算法

步骤 1 – 定义 'curr' 变量以跟踪最新索引。

步骤 2 – 使用 for 循环遍历查询数组。

步骤 3 – 从第 m 个索引获取查询，如果查询对的第一个元素为 1，我们需要对最后更新的字符串进行 'a' 次旋转。

步骤 4 – 在这种情况下，我们将 'curr' 值更新为将对的第二个元素添加到 'curr' 并取其对 26 的模。

步骤 5 – 如果查询对的第一个元素为 2，我们需要打印给定索引处的字符。

步骤 6 – 将 'curr' 变量的值更新为将查询对的第二个元素添加到 'curr' 并取其对 26 的模。

步骤 7 – 访问原始字符串中 'curr' 索引处的字符。此外，在输出中显示字符。

示例

import java.util.*;

public class main {
    static void executeQueries(String alpha, int str_len, int que[][], int que_len) {
        // Current pointer pointing to the starting
        int curr = 0;
        // Traverse array
        for (int m = 0; m < que_len; m++) {
            // Query rotation
            if (que[m][0] == 1) {
                // Update value of curr
                curr = (curr + que[m][1]) % str_len;
            } else {
                int ch = que[m][1];
                // Get the index of the character in rotation
                int index = (curr + ch - 1) % str_len;
                // Show output
                System.out.println(alpha.charAt(index));
            }
        }
    }
    public static void main(String[] args) {
        String alpha = "wqedsdcs";
        int str_len = alpha.length();
        int que[][] = { { 1, 1 }, { 2, 1 },
                { 2, 5 }, { 1, 3 } };
        int que_len = que.length;
        executeQueries(alpha, str_len, que, que_len);
    }
}

输出

q
d

时间复杂度 – O(M)，因为我们逐一执行所有查询。

空间复杂度 – O(1)，因为我们没有使用任何动态空间。

程序员也可以尝试使用朴素方法来解决问题。在朴素方法中，程序员可以旋转字符串以执行第一个查询，并访问更新后的字符串中的字符以执行第二个查询。执行字符串旋转的方法有 1 到 2 种不同的方法；一种是将字符串与其自身连接起来并获取其子字符串。