辗转相除法(GCD)求左旋转字符串

今天在牛客网上做了一道题，题意就是求左旋转字符串。我使用辗转相除法解之，一次性AC通过。实话说，每次写算法一次性通过，甚至一点编译错误都没有，我觉得这就是对我最好的嘉奖。

题目描述： 汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！

这么多废话，实际上就是求左旋转字符串。这里我先给出我的辗转相除法代码：

class Solution {
public:
    string LeftRotateString(string str, int n) {
        int length = str.length();
        if(length <= n)
            return str;
        char *sz = new char[length+1];
        strcpy(sz, str.c_str());
        int times = gcd(length, n);
        while(times--)  //注意这里先判断，再--，所以下面times已经是减过了的
            rotate(sz+times, length, n);
        string res(sz);
        delete []sz;
        return res;
    }
    void rotate(char* sz, int length, int n){
        char* p1 = sz;
        char* p2 = sz + n;
        char tmp = *sz;
        while(p2 != sz){
            *p1 = *p2;
            p1 = p2;
            if(p2 + n > sz + length - 1)
                p2 = sz + (n - ((sz + length) - p2));
            else
                p2 += n;
        }
        *p1 = tmp;
    } 
    int gcd(int m, int n){
        while(n != 0){
            if(m < n)
                std::swap(m, n);
            int tmp = m % n;
            m = n;
            n = tmp;
        }
        return m;
    }
};

思路大致是这样的：对于一个字符串，先求出GCD，也就是字符串长度和要旋转个数的最大公约数。这个最大公约数是我们即将要用到的循环链的数目。也就是执行rotate循环的次数。

现在解释什么是循环链。比如“1234”，我们求它把前面3个字符放到后面的情况，即n=3。此时GCD(4,3)=1，即times=1。那么分析rotate函数。由于在该函数中我们用tmp保存了sz，你需要用tmp保存了这个值，也就是p1的值，我们就可以使用*p2覆盖该位置的值了，并且p2=p1+n。对于该情况，rotate函数依照代码执行的流程为(用下划线表示空位，也就是p1指向的将被覆盖的位置):

_ 2 3 4 -> 4 2 3 _ -> 4 2 _ 3 -> 4 _ 2 3 -> 4 1 2 3(这是最后一步:*p1=tmp)

如上，这个rotate函数只需执行一次就可以达到目的，旋转3个字符要求达成。这就叫做一次循环链，最大公约数times的值就说明了这个问题。

再举一例，有两个循环链的例子：还是“1234”，求把前两个字符放在后面的情况，即n=2。GCD(4，2)=2，可知有两个循环链。我们来验证一下：

第一次：times=1(由于times--),所以p1=2,p2=4(p2=p1+n)，所以循环流程：

1 _ 3 4 -> 1 4 3 _ -> 1 4 3 2

第二次：times=0，并且p1=1,p2=3，循环流程为：

_ 4 3 2 -> 3 4 _ 2 -> 3 4 1 2

没错，循环两次就成功解决问题了，所以最大公约数就是循环链的数目，也就是执行rotate函数的次数。

我在牛课网上看了，大多数人可能使用没有改变内存的substr，有的人使用三次reverse，没有见到有人使用GCD。我之前也用reverse，但是现在熟悉了新技能，那就用它吧。

对了，我的思路是以前剖析STL源代码学习的，如果感兴趣可以看STL rotate函数的实现，对不同迭代器重载不同的版本，其中RandomIterator版本使用的就是GCD。