数据结构
网络
关系型数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++字符串原地变换算法
对于给定的字符串，将所有偶数位置的元素转移到字符串的末尾。在转移元素时，保持所有偶数位置和奇数位置元素的相对顺序不变。
例如，如果给定的字符串是“a1b2c3d4e5f6g7h8i9j1k2l3m4”，则将其原地变换为“abcdefghijklm1234567891234”，时间复杂度为O(n)。
步骤如下：
裁剪出大小为3^k + 1形式的最高前缀子字符串。此步骤中，我们找到最大的非负整数k，使得3^k+1小于或等于n（字符串长度）。
实现循环领导迭代算法（如下所述），从索引1、3、9……开始到这个子字符串。循环领导迭代算法将此子字符串的所有项转移到它们正确的位置，这意味着所有字母都移动到子字符串的左半部分，所有数字都移动到子字符串的右半部分。
递归地处理剩余的子字符串，实现步骤1和步骤2。
目前，我们只需要将处理后的子字符串连接在一起。从任意一端开始（例如从左侧），选择两个子字符串并执行以下步骤：
反转第一个子字符串的后半部分。
反转第二个子字符串的前半部分。
将第一个子字符串的后半部分和第二个子字符串的前半部分一起反转。
重复步骤4，直到所有子字符串都被连接起来。这与k路合并类似，其中第一个子字符串与第二个子字符串合并。结果与第三个子字符串合并，依此类推。
基于上述算法的代码如下：
// C++ application of above approach
#include <bits/stdc++.h>
using namespace std;
// A utility function to swap characters void swap ( char* a1, char* b1 ) {
char t = *a1; *a1 = *b1; *b1 = t;
}
// A utility function to reverse string str1[low1..high1]
void reverse ( char* str1, int low1, int high1 ) {
while ( low < high ) {
swap(&str1[low1], &str1[high1] ); ++low1; --high1;
}
}
// Cycle leader algorithm to shift all even
// positioned elements at the end.
void cycleLeader ( char* str1, int shift1, int len1 ) {
int j;
char item1;
for (int i = 1; i < len1; i *= 3 ) {
j = i; item1 = str1[j + shift1];
do{
// odd index if ( j & 1 )
j = len1 / 2 + j / 2;
// even index or position else j /= 2;
// keep the back-up of element at new index or position
swap (&str1[j + shift1], &item1);
}
while ( j != i );
}
}
// The main function to convert a string. This function
// mainly implements cycleLeader() to convert void moveNumberToSecondHalf( char* str1 ) {
int k, lenFirst1; int lenRemaining1 = strlen( str1); int shift1 = 0;
while ( lenRemaining1) {
k = 0;
// Step 1: Find the highest prefix
// subarray of the form 3^k + 1
while ( pow( 3, k ) + 1 <= lenRemaining1)
k++; lenFirst1 = pow( 3, k - 1 ) + 1;
lenRemaining1 -= lenFirst1;
// Step 2: Implement cycle leader algorithm
// for the highest subarray cycleLeader ( str1, shift1, lenFirst1 );
// Step 4.1: Just opposite or reverse the second half of first subarray reverse ( str1,
shift1/2, shift1 - 1 );
// Step 4.2: Just opposite or reverse the first half of second sub-string. reverse ( str1,
shift1, shift1 + lenFirst1 / 2 - 1 );
// Step 4.3 Just opposite or reverse the second half of first sub-string and first half of
second sub-string together reverse ( str1, shift1 / 2, shift1 + lenFirst1 / 2 - 1 );
// Now increase the length of first subarray Shift1 += lenFirst1;
}
}
// Driver program to verify or test above function int main() {
char str1[] = "a1b2c3d4e5f6g7"; moveNumberToSecondHalf( str1 ); cout<<str1; return 0;
}输出
abcdefg1234567
更新于：2020年1月29日
浏览量：118
广告