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"

输出

l

解释

• 第一个查询后，字符串将变为’comewel’。

• 第二个查询后，字符串将变为’mewelco’。

• 第三个查询后，字符串将变为’elcomew’。

• 在最后一个查询中，它打印第二个字符，即’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。之后，将结果值赋给index变量。

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

输出

m
n
k

时间复杂度 – O(M)，因为我们遍历给定的查询列表。

空间复杂度 – O(1)，因为我们使用常量空间。

我们根据给定的条件执行字符串的左旋转。程序员也可以尝试执行包含右字符串旋转的查询。