C++程序 在常数时间内查询给定字符串的旋转和第K个字符
给定一个字符串 str ,任务是在给定字符串上执行以下类型的查询:
- (1, K): 将字符串左旋转 K 个字符。
- (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字符。
下面是以上方法的实现:
输出
时间复杂度: O(Q), 其中Q是查询数量。
辅助空间: O(1)