今天在牛客網上做了一道題，題意就是求左旋轉字元串。我使用輾轉相除法解之，一次性AC通過。實話說，每次寫演算法一次性通過，甚至一點編譯錯誤都沒有，我覺得這就是對我最好的嘉獎。 題目描述： 彙編語言中有一種移位指令叫做迴圈左移（ROL），現在有個簡單的任務，就是用字元串模擬這個指令的運算結果。對於一個給定 ...
今天在牛客網上做了一道題，題意就是求左旋轉字元串。我使用輾轉相除法解之，一次性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。
