Python3程序，用于在恒定时间内查询给定字符串的旋转和第K个字符

在这个问题中，我们需要根据给定的规则执行查询并打印更新后的字符串的字符。我们将使用两种不同的方法来解决这个问题。在第一种方法中，我们将使用字符串旋转的概念，在第二种方法中，我们将使用索引定制的方法。

问题陈述 - 我们被要求在字符串上执行给定的查询。我们已经给出了查询数组，每个查询包含两个整数。

按照下面的语句执行给定的查询。

(1, l) – 我们需要将字符串左旋转l次。
(2, l) – 我们需要访问第l个位置上的字符。这里，1 <= l <= n。

示例示例

输入

queries = [[1, 3], [2, 3], [2, 4], [2, 2]], s = "vdflkmng"

输出

m, n, k

解释 - 让我们执行数组中给出的所有四个查询。

对第一个查询中的字符串进行3次左旋转。最终字符串将为’lkmngvdf’。
打印第三个字符，即’m’。
打印第四个字符，即’n’。
打印第二个字符，即’k’。

输入

queries = [[1, 3], [1, 2], [1, 3], [2, 2]], s = "welcome"

输出

解释

第一个查询后，字符串将变为’comewel’。
第二个查询后，字符串将变为’mewelco’。
第三个查询后，字符串将变为’elcomew’。
最后一个查询中，打印第2个字符，即’l’。

方法1

在这种方法中，我们将给定的字符串分为两部分，然后重新连接以执行N次左旋转。然后，我们从第二个查询中访问给定索引处的字符。

算法

步骤1 – 在第一步中，我们需要遍历所有查询的数组。

步骤2 – 如果que[m][0] 1，则将字符串s进行que[m][1]次左旋转，并将其存储到s中。

步骤2.1 – 要进行que[m][1]次左旋转，我们可以将字符串从索引m分为两部分，然后连接右部分和左部分。

步骤3 – 如果que[m][0] 2，则需要从索引que[m][1]处打印字符。

步骤4 – 访问给定索引处的字符，并在输出中显示出来。

示例

def executeQueries(s, str_len, que, que_len):
    # Traverse query
    for m in range(que_len):
        # String rotation
        if que[m][0] == 1:
            # Rotate the string by que[m][1] to the left
            s = s[que[m][1]:] + s[:que[m][1]]
        else:
            index = que[m][1] - 1
            # Show character
            print(s[index])
# Driver code
if __name__ == "__main__":
    s = "vdflkmng"
    length = len(s)
    queries = [[1, 3], [2, 3], [2, 4], [2, 2]]
    queries_length = len(queries)
    executeQueries(s, length, queries, queries_length)

输出

m
n
k

时间复杂度 – O(M*N)，因为我们将字符串分为两部分并遍历列表。

空间复杂度 – O(N)，因为我们存储了旋转字符串。

方法2

这种方法是上面方法的优化版本。在这里，我们创建一个指针指向最后一个索引。当执行查询时，我们更新指针的值，这有助于节省时间和空间。

算法

步骤1 - 定义ind_ptr变量并初始化为零，代表索引指针。

步骤2 - 使用循环遍历列表。

步骤3 - 如果que[m][0]等于1，我们需要操作索引指针的值。

步骤3.1 - 将que[m][1]添加到ind_ptr，对结果值进行26的模，并再次赋值给ind_ptr变量。

步骤4 - 如果que[m][0]等于2，我们需要打印位于索引que[m][1]位置的字符。

步骤5 - 将que[m][1] - 1添加到ind_ptr变量，并对其进行26的模。然后，将结果值赋给索引变量。

步骤6 - 访问索引处的字符并将其打印出来显示在输出中。

示例

def executeQueries(s, str_len, que, que_len):
    # Starting pointer
    ind_ptr = 0
    # Traverse query
    for m in range(que_len):
        # String rotation
        if que[m][0] == 1:
            # Change index pointer value
            ind_ptr = (ind_ptr + que[m][1]) % str_len
        else:
            index = que[m][1]
            # Get the rotational index of the character
            index = (ind_ptr + index - 1) % str_len
            # Show character
            print(s[index])
if __name__ == "__main__":
    s = "vdflkmng"
    length = len(s)
    queries = [[1, 3], [2, 3], [2, 4], [2, 2]]
    queries_length = len(queries)
    executeQueries(s, length, queries, queries_length)