剑指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，您已经看到，m=3时，p2恰好指到了数组最后一个元素，每m个一组正好一一对应。于是，上述思路没有问题。但是每m个一组有剩余时怎么办？假设abcde，还能如上面的方法解决吗？这样就不可以了，那样就数组越界了。所以我们要特殊处理尾部不够m个一组的元素。

就举这个例子，对abcdefghij序列进行左旋转操作：

如果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之前，得到最终序列，代码编写如下：

#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!!!）
*   来源：http://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;
}

转载： 程序员编程艺术：第一章、左旋转字符串

自己按自己思路有改动。