左旋轉字元串 left rotate string

左旋轉字元串

題目：字元串的左旋轉操作：把字元串前面的若幹字元移到字元串的後面。例如：字元串abcdefg左旋轉2位得到cdefgab。請實作左旋轉字元串函數，要求對于長度為n的字元串，時間複雜度為O(n)，輔助記憶體為O(1)。

算法思想： 可以利用三次字元串反轉操作，來達到左旋轉字元串的目的： 1.反轉字元串的前半段； 2.反轉字元串的後半段； 3.反轉整個字元串。

代碼如下：

#include<iostream>
#include<string.h>

using namespace std;

// 本函數對string的子串進行反轉操作
// start和end分别指明了字串的起始位置和結束位置（左閉右開區間）
void revert_string(char* string, int start, int end)
{
	int i=start, j=end-1;
	char tmp;
	while(i<j)
	{
		tmp = *(string+i);
		*(string+i) = *(string+j);
		*(string+j) = tmp;
		i++;
		j--;
	}

}

// 進行三次反轉操作就可以完成左字元串旋轉操作
void leftRotateString(char* string,  int i)
{
	int len = strlen(string);
	revert_string(string,0,i);
	revert_string(string,i,len);
	revert_string(string,0,len);
}

int main(){
	// declaring string as a char pointer instead of a char array
	// will cause the program to crash, i.e., using the following declaration
	//        char* string = "This_is_a_sample_string";
	// will make the program crash
	char string[] = "This_is_a_sample_string";
	leftRotateString(string, 4);
	cout<<string<<endl;
	return 0;
}
           

輸出如下：

“_is_a_sample_stringThis”

除了上面的算法，還有一個著名的雜技算法。移動S[0]到臨時變量t，然後移動S[K]到S[0]；移動S[2K]到S[K]，依此類推（将S中的所有下标對n取模），直到傳回到取S[0]中的元素，此時改為從t取值然終止過程。當n為12，k為3時，元素按如下順序移動（如下圖，畫得太醜了，莫怪）。如果該過程沒有移動全部的元素，則從S[1]開始再次移動，直到所有的元素都已經移動位置。 代碼如下：

#include<iostream>
 #include<string>
 using namespace std;
 
 //求兩個整數i，j的最大公約數
 int gcd(int i,int j)
 {
     while(i != j)
     {
         if(i > j)
             i -= j;
         else
             j -= i;
     }
     return i;
 }
 
 
 //左旋轉字元串函數，将pStr字元串向左旋轉k位，
 //first指向pStr[i],second指向pStr[2i]，以此類推
 char* LeftRotateString(char* pStr,int k)
 {
     if(pStr == NULL || k < 1)
         return 0;
 
     int n = strlen(pStr);
     
     //共進行i趟循環，i為n，k的最大公約數
     for(int i = 0;i < gcd(n,k);++i)
     {
         char temp = pStr[i];
         int first = i;
         while(1)
         {
             int second = (first + k) % n;
 
             if(second == i)
                 break;
             
             pStr[first] = pStr[second];
             first = second;
         }
 
         //将臨時變量中的字元存至每一趟的循環的最後一個字元中
         pStr[first] = temp;
     }
     return pStr;
 }
  
 int main()
 {
     string demo("abcdefgh");
     cout<<demo<<endl;
 
     LeftRotateString(&demo[0],3);
 
     cout<<demo<<endl;
     return 0;
 }