C++ 中的原地字符串转换算法

在本文中，我们将讨论 C++ 中字符串转换的就地算法，并提供几个示例。

在此算法中，将给定字符串中所有位于偶数位置的项移动到字符串的末尾。在移动它们时，保持所有位于偶数和奇数位置的元素的相对顺序不变。

例如，如果字符串是“a1b2c3d4e5f6g7h8i9j1k2l3m4”，则将其就地转换为“abcdefghijklm1234567891234”，时间复杂度为O(n)。

以下是步骤：

删除形式为3k + 1的最大尺寸前缀子字符串。在此阶段，我们找到最大的非负数 k，使得 3k+1 小于或等于 n（字符串长度）。

• 对此子字符串实施循环领导者迭代技术，从索引 1、3、9 等开始。使用循环领导者迭代技术将此子字符串的所有元素重新定位到其正确位置，这意味着所有字母都移动到子字符串的左半部分，所有数字都移动到右半部分。
• 应用第一阶段和第二阶段，迭代处理剩余的子字符串。
• 我们目前只需要合并已处理的子字符串。从任意一端（例如左端）开始，选择两个子字符串，并执行以下操作：
• 只需翻转或反转第一个子字符串的后半部分。
• 只需反转或翻转第二个子字符串的前半部分。
• 只需将第二个子字符串的前半部分与第一个子字符串的后半部分组合起来，以反转或翻转它们。
• 重复步骤 4，直到所有子字符串都连接起来。这与 k 路合并相同，其中第一个和第二个子字符串已连接。结果与第三个合并，依此类推。

示例

让我们用一个例子来更好地理解它：

请注意，下面示例中使用的值包括 10、11 和 12。仅将这些值用作单个字符。为了提高可读性，使用了这些值。

• 在分解成 3k+1 形式的大小后，创建了两个大小为 10 的子字符串。第三个和第四个子字符串分别使用大小 4 和 2 创建。

• 在第一个子字符串使用循环领导者迭代算法后：

• 当第二个子字符串受到循环领导者迭代算法的影响时：

• 当第三个子字符串受到循环领导者迭代算法的影响时：

• 当第四个子字符串受到循环领导者迭代算法的影响时：

合并第一个和第二个子字符串：

1. 第二个子字符串的前半部分和第一个子字符串的后半部分被反转。

2. 第二个子字符串的前半部分和第一个子字符串的后半部分，都反转后合并（它们合并了，所以现在只有三个子字符串）。

再次合并第一个和第二个子字符串：

1. 第二个子字符串的前半部分和第一个子字符串的后半部分被反转。

2. 第二个子字符串的前半部分和第一个子字符串的后半部分，都反转后合并（它们合并了，所以现在只有两个子字符串）。

连接第一个和第二个子字符串：

1. 第二个子字符串的前半部分和第一个子字符串的后半部分被反转。

2. 第二个子字符串的前半部分和第一个子字符串的后半部分，都反转后合并（它们现在是一个子字符串）。

根据上述算法，代码如下所示：

示例 1

输出

oellHWrldo

示例：2

让我们再举一个例子来说明 C++ 中字符串转换的就地算法。

输出

sihT si a elpmas ecnetnes ot esrever sdrow

重要提示

• 如果数组大小已经是3k+1的形式，则可以直接使用循环领导者迭代算法。无需连接。
• 只有大小为 3k + 1 形式的数组才能使用循环领导者迭代技术。