旋转和查询字符串中第K个字符的Java程序，要求时间复杂度为常数

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

问题陈述： 给定字符串alpha和包含一对数字的数组“que”。任务是对字符串alpha执行数组中给定的查询操作。

遵循以下查询操作规则：

(1, a) – 将给定字符串进行a次左旋转。
(2, a) – 从第a个位置打印字符。

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

示例：

输入：

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

输出

q, d

解释 - 让我们逐个执行字符串上的所有查询。

第一个查询将字符串旋转1次，更新后的字符串将为’qedsdcsw’。
第二个查询打印第一个位置上的字符，即’q’。
第三个查询打印第五个位置上的字符，即’d’。
第四个查询进行3次左旋转。

输入

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

输出

o, u

解释

执行第一个查询后，字符串变为 ‘utorialspoint’。
更新后字符串第三个位置的字符是 ‘o’。
执行第三个查询后，字符串变为 ‘pointtutorials’。
第七个位置的字符是 ‘u’。

方法1

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

算法

步骤1 - 定义变量 ‘curr’ 来跟踪最新的索引。

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

步骤3 - 从第m个索引获取查询，如果查询对中的第一个元素是1，则需要对最后修改的字符串进行 ‘a’ 次旋转。

步骤4 - 在这种情况下，我们通过将对对中的第二个元素添加到 ‘curr’，并用26取模来更新 ‘curr’ 的值。

步骤5 - 如果查询对中的第一个元素是2，则需要打印给定索引处的字符。

步骤6 - 将查询对中的第二个元素添加到 ‘curr’，并用26取模来更新 ‘curr’ 的值。

步骤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);
    }
}