左旋转字符串 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;
 }