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

编程爱好者联盟 2017-01-18

今天在牛客网上做了一道题,题意就是求左旋转字符串。我使用辗转相除法解之,一次性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。