翻译：对于M个查询，反转给定字符串的范围

在这个问题中，我们将根据数组值对给定的字符串执行 M 次反向查询。

解决问题的简单方法是根据给定的数组值反转每个字符串段。

优化的方法使用的逻辑是，当我们将相同的子字符串反转两次时，我们得到原始字符串。

问题陈述 - 我们给出了一个包含字母字符的字母字符串。此外，我们还给出了一个大小为 M 的 arr[] 数组，其中包含正整数。我们需要对给定的字符串执行 M 次操作并返回最终的字符串。

在每个操作中，我们需要取出 arr[i] 并将子字符串 arr[i] 转换为 N − arr[i] + 1。

示例示例

输入

雷雷

输出

雷雷

解释 

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

• 执行第二个查询后，我们得到了 'tqrsp'。

输入

雷雷

输出

雷雷

解释 − 如果我们对同一个查询执行偶数次，我们会得到相同的字符串。

输入

雷雷

输出

雷雷

解释 - 如果我们执行相同的查询奇数次，我们会得到相反的字符串。

方法1

在这种方法中，我们将使用reverse()方法来反转子字符串。我们将使用给定的查询获取起始和结束指针，并反转给定字符串的子字符串。

算法

步骤 1 - 开始遍历查询快照。

第2步 - 使用arr[p] - 1初始化'left'变量。

步骤 3 - 使用 str_len - arr[p] + 1 初始化“right”变量。

步骤 4 - 使用reverse()方法将子字符串从左指针反转到右指针。

示例

雷雷

输出

雷雷

时间复杂度 − O(N*M)，用于反转子字符串 M 次。

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

方法二

在这种方法中，我们将使用给定的查询计算该特定索引以及包含在反转中的次数。如果任何索引被包含偶数次，我们不需要反转它。如果在所有给定查询中任何索引包含奇数次，我们需要反转特定索引处的字符。

算法

步骤 1 -初始化长度等于字符串长度的 'cnt' 列表，用 0 存储特定索引在叉子中出现的次数。

步骤 2 - 遍历给定查询的数组，并根据当前查询获取字符串的左指针和右指针。

步骤3 - 还执行changeRange()函数，根据当前查询的左指针和右指针更新'cnt'列表。

步骤 3.1 - 在changeRange()函数中，增加“cnt”列表中“left”索引处的值。

第3.2步 - 减少“cnt”列表中位于“right + 1”光标右边的所有值。

这里，我们需要将‘cnt’列表中[左，右]范围内的所有值加1。因此，我们只将 cnt[left] 增加 1，因为采用前缀和将使所有值增加 1，即“左”索引的右侧。另外，我们不想增加 [right, str_len] 索引之间的 cnt 值，因此我们已经将其减 1，因为前缀和会将其增加 1。

步骤 4 - 接下来，执行 getPrefixSum() 函数来计算 ‘cnt’ 列表的前缀和。

步骤 4.1 - 在 getPrefixSum() 函数中，遍历字符串并将前一个元素的值添加到当前元素。

步骤 5 - 后面，以逆序遍历‘cnt’列表。如果当前元素是奇数，则将其追加到‘tmp’字符串中。

步骤 6 - 使用0初始化‘p’和‘q’，按照原始顺序遍历‘cnt’列表。

步骤 7 − 如果‘cnt’列表中的当前元素是奇数，则使用tmp[q]更新alpha[p]。

步骤 8 - 最后，返回字母字符串。

示例

的中文翻译为：

示例

雷雷

输出

雷雷

时间复杂度 − O(M*N + N)，其中 O(M*N) 是根据查询更新 ‘cnt’ 列表，O(N) 是更新给定的字符串。

空间复杂度 - 使用 'cnt' 列表为 O(N)。

在第一个方法中，我们使用了reveres()方法来执行给定字符串上的所有查询。在第二个方法中，我们使用了外部技术来计算特定索引在生成中出现的次数.

以上是翻译：对于M个查询，反转给定字符串的范围的详细内容。更多信息请关注PHP中文网其他相关文章！