162
剑指Offer详解之左旋转字符串
（1）暴力移位法
这种方法可能是最直观，最容易想出的方法。但这也是最坏的方法。时间复杂度挺高，用这种方法容易超时。
这种方法是一位一位的移动实现左旋转操作。
【代码】
#include <stdio.h>
#include <malloc.h>
#include <string.h>
char *str;
char* Reverse(char* str,int n){
if(str == NULL || n < 0){
return "";
}
int len = strlen(str);
int i;
char temp;
//循环左移n位
while(n--){
//左移
//保存第一个字符
temp = str[0];
for(i = 1;i < len;i++){
str[i-1] = str[i];
}
str[len-1] = temp;
}
return str;
}
int main() {
int i,n;
str = (char*)malloc(sizeof(char)*1001);
while(scanf("%s",str) != EOF){
scanf("%d",&n);
//左旋转
str = Reverse(str,n);
//输出
for(i = 0;i < strlen(str);i++){
printf("%c",str[i]);
}
printf("\n");
}//while
return 0;
}
UDBOJ 4对上述字符串循环左移4次，8次，12次。。。。。(n % len )效果是一样的
左移次数：n % len n原始左移次数 len字符串长度
【代码】
char* Reverse(char* str,int n){
if(str == NULL || n < 0){
return "";
}
int len = strlen(str);
int i;
char temp;
//对左移次数进行优化
n = n % len;
//循环左移n位
while(n--){
//左移
//保存第一个字符
temp = str[0];
for(i = 1;i < len;i++){
str[i-1] = str[i];
}
str[len-1] = temp;
}
return str;
}
（2）指针翻转法
咱们先来看个例子，如下：
abcdefghi，若要让abc移动至最后的过程可以是：abcdefghi->defabcghi->defghiabc
如此，我们可定义俩指针，p1指向ch[0]，p2指向ch[m]；
一下过程循环m次，交换p1和p2所指元素，然后p1++, p2++；。
第一步，交换abc 和def ，abcdefghi->defabcghi
第二步，交换abc 和ghi，defabcghi->defghiabc
整个过程，看起来，就是abc作为一组一步一步向后移动
abcdefghi
defabcghi
defghiabc
//最后的 复杂度是O（m+n）
abcdefghi，若要让abc移动至最后的过程可以是：abcdefghi->defabcghi->defghiabc
如此，我们可定义俩指针，p1指向ch[0]，p2指向ch[m]；
一下过程循环m次，交换p1和p2所指元素，然后p1++, p2++；。
第一步，交换abc 和def ，abcdefghi->defabcghi
第二步，交换abc 和ghi，defabcghi->defghiabc
整个过程，看起来，就是abc作为一组一步一步向后移动
abcdefghi
defabcghi
defghiabc
//最后的 复杂度是O（m+n）
由上述例子九个元素的序列abcdefghi，您已经看到，m=3时，p2恰好指到了数组最后一个元素，每m个一组正好一一对应。于是，上述思路没有问题。但是每m个一组有剩余时怎么办？假设abcde，还能如上面的方法解决吗？这样就不可以了，那样就数组越界了。所以我们要特殊处理尾部不够m个一组的元素。
就举这个例子，对abcdefghij序列进行左旋转操作：
如果abcdefghij要变成defghijabc：
1. defabcghij
2. defghiabcj //最后一个j不够一组m个要单独处理
3. defghiabjc //我们需要一次一次交换移至前面
4. defghiajbc
5. defghijabc
下面，再针对上述过程，画个图清晰说明下，如下所示：
如果abcdefghij要变成defghijabc：
1. defabcghij
2. defghiabcj //最后一个j不够一组m个要单独处理
3. defghiabjc //我们需要一次一次交换移至前面
4. defghiajbc
5. defghijabc
下面，再针对上述过程，画个图清晰说明下，如下所示：
总结：
1、首先让p1=ch[0]，p2=ch[m]，即让p1，p2相隔m的距离，可以理解为每m个一组，第一组和后每组对应交换；
2、判断p2+m-1是否越界，即判断最后一组是不是构成一组。如果不能构成一组就不能一一对应交换，如果没有越界转到3，否则转到4。
3、不断交换*p1与*p2，然后p1++，p2++，循环m次，然后转到2。
4、此时p2+m-1已经越界，即最后一组不能构成一组，不能一一对应交换，需处理尾巴。
过程如下：
4.1 通过n-p2得到p2与尾部之间元素个数r，即我们要前移的元素个数。
4.2 以下过程执行r次：
ch[p2]<->ch[p2-1]，ch[p2-1]<->ch[p2-2]，....，ch[p1+1]<->ch[p1]；p1++；p2++；
所以，之前最初的那个左旋转九个元素abcdefghi的思路在末尾会出现问题的（如果p2后面有元素就不能这么变，例如，如果是处理十个元素，abcdefghij?对的，就是这个意思），解决方法：
def ghi abc jk
当p1指向a，p2指向j时，由于p2+m越界，那么此时p1，p2不要变
这里p1之后（abcjk)就是尾巴，处理尾巴只需将j,k移到abc之前，得到最终序列，代码编写如下：
1、首先让p1=ch[0]，p2=ch[m]，即让p1，p2相隔m的距离，可以理解为每m个一组，第一组和后每组对应交换；
2、判断p2+m-1是否越界，即判断最后一组是不是构成一组。如果不能构成一组就不能一一对应交换，如果没有越界转到3，否则转到4。
3、不断交换*p1与*p2，然后p1++，p2++，循环m次，然后转到2。
4、此时p2+m-1已经越界，即最后一组不能构成一组，不能一一对应交换，需处理尾巴。
过程如下：
4.1 通过n-p2得到p2与尾部之间元素个数r，即我们要前移的元素个数。
4.2 以下过程执行r次：
ch[p2]<->ch[p2-1]，ch[p2-1]<->ch[p2-2]，....，ch[p1+1]<->ch[p1]；p1++；p2++；
所以，之前最初的那个左旋转九个元素abcdefghi的思路在末尾会出现问题的（如果p2后面有元素就不能这么变，例如，如果是处理十个元素，abcdefghij?对的，就是这个意思），解决方法：
def ghi abc jk
当p1指向a，p2指向j时，由于p2+m越界，那么此时p1，p2不要变
这里p1之后（abcjk)就是尾巴，处理尾巴只需将j,k移到abc之前，得到最终序列，代码编写如下：
#include <stdio.h>
#include <malloc.h>
#include <string.h>
char *str;
void Reverse(char* str,int n){
if(str == NULL || n <= 0){
return;
}
int len = strlen(str);
int pre = 0;
int p = n;
char temp;
//len % n n个一组，不够一组的个数
//len - n - len % n 表示总个数减去最前一组减去最后不够一组的个数
//交换次数
int count = len - n - len % n;
while(count--){
//交换
temp = str[pre];
str[pre] = str[p];
str[p] = temp;
pre++;
p++;
}
//处理最后尾部不够一组的元素
//rear为尾部左移元素个数
int rear = len - p;
while(rear--){
//左移
int i = p;
while(i > pre){
temp = str[i];
str[i] = str[i-1];
str[i-1] = temp;
i--;
}
p++;
pre++;
}
}
int main() {
int i,n;
str = (char*)malloc(sizeof(char)*1001);
while(scanf("%s",str) != EOF){
scanf("%d",&n);
//左旋转
//注意一下n需要取余就可以了，不能超过字符串自身的长度
n = n % strlen(str);
Reverse(str,n);
//输出
for(i = 0;i < strlen(str);i++){
printf("%c",str[i]);
}
printf("\n");
}//while
return 0;
}
（3）三步翻转法
/*********************************
* 日期：2013-12-02
* 作者：SJF0115
* 题号: 题目1362：左旋转字符串（Move!Move!!Move!!!）
* 来源：https://ac.jobdu.com/problem.php?pid=1362
* 结果：AC
* 来源：剑指Offer
* 总结：
**********************************/
#include <stdio.h>
#include <malloc.h>
#include <string.h>
char *str;
//反转单词
void ReverseWord(char* words,int begin,int end){
int temp;
if(words == NULL || begin > end || begin < 0){
return;
}
//反转
while(begin < end){
temp = words[begin];
words[begin] = words[end];
words[end] = temp;
begin ++;
end --;
}
}
char* Reverse(char* str,int n){
if(str == NULL || n < 0){
return "";
}
int len = strlen(str);
//分成两部分（1）前n项（2）剩余项
//反转前n个
ReverseWord(str,0,n-1);
//反转剩余
ReverseWord(str,n,len-1);
//全部反转
ReverseWord(str,0,len-1);
return str;
}
int main() {
int i,n;
str = (char*)malloc(sizeof(char)*1001);
while(scanf("%s",str) != EOF){
scanf("%d",&n);
//左旋转
//注意一下n需要取余就可以了，不能超过字符串自身的长度
n = n % strlen(str);
str = Reverse(str,n);
//输出
for(i = 0;i < strlen(str);i++){
printf("%c",str[i]);
}
printf("\n");
}//while
return 0;
}
自己按自己思路有改动。
最后更新：2017-04-03 14:54:29