编程爱好者联盟 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。