学步园

题目描述：将一个n元一维向量向左旋转i个位置。例如：当n=8且i=3时，向量abcdefgh旋转为defghabc。

其实这类问题方法有很多中，我就介绍两种比较特殊的方法：一种时间复杂度为O(n),空间复杂度O(1),另一种时间复杂度为O(1),空间复杂度为O(n)(以上空间复杂度不包括存储原字符串的空间)

方法一的思路：将字符串分为两个向量ab，a为前i-1个字符组成的向量，b为剩下字符组成的向量；首先将a逆序，得到a(r)b，再将b逆序，得到a(r)b(r)，最后将整体逆序得到(a(r)b(r))(r) = ba;

例如字符串abcdefgh左旋转i=3，则a=abc，b=defgh

reverse(str, 0, i-1)  => cbadefgh

reverse(str, i, len-1) => cbahgfed

reverse(str, 0, len-1) => defghabc

这里有个细节需要注意，当i大于等于字符串的长度时，需要对i相对于len求余，即i = i%len

具体代码如下：

#include <iostream>
#include <cstring>
using namespace std;

void exch(char &a, char &b)	{ char temp = a; a=b; b=temp; }

void reverse(char *str, int start, int end)  //从start到end逆序str中的字符
{
	char *p=NULL;
	int i=start, j=end;
	while(i<j)
	{
		exch(*(str+i),*(str+j));
		i++;
		j--;	
	}
}

void rev_str(char *str, int shift)
{
	int len = strlen(str);
	if(shift>=len)	shift %= len;
	reverse(str, 0, shift-1);
	reverse(str, shift, len-1);
	reverse(str, 0, len-1);	
}

int main(void)
{
	const int SHIFT = 9;
	char str[100]="123456";
	rev_str(str, SHIFT);
	cout << str << endl;
	return 0;
}

方法二，典型的用空间换取时间

具体思路：申请一个与原字符串等大的内存空间的临时数组，首先将b向量(将字符串分为两个向量的思路与方法一等同)复制到临时数组中，再将a向量复制到临时数组中，最后将临时数组的内容复制到原字符串中

strncpy(temp, &str[shift], len-shift)

strnpy(&temp[len-shift], str, shift);

temp[len]='\0';                     //这是细节需要特别注意，因为之前temp并不是一个字符串，没有结束标志

strcpy(str, temp);

具体实现代码如下：

#include <iostream>
#include <cstring>
#include <cstdlib>
using namespace std;

void rev_str(char *str, int shift)
{
	int step=0;
	int len = strlen(str);
	shift = shift>=len ? shift%len : shift;
	char *temp = (char *)malloc(len+1);
	//在内存中进行相应位置的拷贝字符，从而达到字符旋转的目的
	strncpy(temp, &str[shift], len-shift);
	strncpy(&temp[len-shift], str, shift);
	temp[len]='\0';
	strcpy(str, temp);
}
int main(void)
{
	const int SHIFT = 2;
	char str[] = "123456";
	rev_str(str, SHIFT);
	cout << str << endl;
	return 0;
}

以上方法知识其中的两种，若有更好的方法，或者我的方法有什么不妥，可以与我交流，互相学习！