資料結構
網路
關係型資料庫管理系統(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
廣告