题目描述
给定一个字符串，要求把字符串前面的若干个字符移动到字符串的尾部，如把字符串“abcdef”前面的2个字符'a'和'b'移动到字符串的尾部，使得原字符串变成字符串“cdefab”。请写一个函数完成此功能，要求对长度为n的字符串操作的时间复杂度为 O(n)，空间复杂度为 O(1)。
暴力移位法
初看此题，可能最先想到的方法是按照题目所要求的，把需要移动的字符一个一个地移动到字符串的尾部，如此我们可以实现一个函数 LeftShiftOne(char* s, int n) ，以完成移动一个字符到字符串尾部的功能，代码如下所示：
#define MAX 1024
#include <stdio.h>
#include <string.h>
void Leftshift(char *str,size_t n)
{
char ch = str[0];
for(int i = 1;i < n;i++)
{
str[i-1] = str[i];
}
str[n-1] = ch;
}
void LeftRotateString(char *str,size_t n,int m)
{
for(int i=0;i<m;i++)
{
Leftshift(str,n);
}
}
int main()
{
char str[MAX]="abcdefghijklmnopqrstuvwxyz";
size_t size = strlen(str);
LeftRotateString(str,size,3);
printf("%s\n",str);
}
针对长度为n的字符串来说，假设需要移动m个字符到字符串的尾部，那么总共需要 mn 次操作，同时设立一个变量保存第一个字符，如此，时间复杂度为O(m n)，空间复杂度为O(1)，空间复杂度符合题目要求，但时间复杂度不符合要求。
三步反转法
对于任意字符串，假设我们初始字符串为abcdef，我们移动后的字符串为defabc，可以按照如下步骤实现：
令X=abc Y=def即将原字符串分为两部分
一：反转X=abc---->X=cba
二：反转Y=def----->Y=fed
三：反转整体字符串cbafed-------->defabc
复杂度分析假设字符串长度为n,我们最多移动了3*n次，即时间复杂度为O(n),空间复杂度O(1)，符合题目要求。
/*
Name:旋转 字符串
Copyright: 52coder.net
Author: 52coder
Date: 04/09/17 23:44
Description:旋转字符串
*/
#define MAX 1024
#include <stdio.h>
#include <string.h>
/*反转字符串*/
void ReverseString(char *str,int from,int to)
{
while(from < to)
{
char t = str[from];
str[from++] = str[to];
str[to--] = t;
}
}
void LeftRotateString(char *str,int n,int m)
{
m %= n;
if(0 == m)
{
printf("No need to move str.\n");
return;
}
ReverseString(str,0,m-1);
ReverseString(str,m,n-1);
ReverseString(str,0,n-1);
}
int main()
{
char str[MAX]="abcdefghik";
int len = 10;
/*移动13次==移动三次，移动len次后复原*/
int mov = 21;
LeftRotateString(str,len,mov);
printf("%s\n",str);
}