第二節：兩指針逐步翻轉

思路：
abc defghi，要 abc 移動至最后
abc defghi->def abcghi->def ghiabc
定義倆指針， p1 指向 ch[0]， p2 指向 ch[m]；
一下過程循環 m 次，交換 p1 和 p2 所指元素，然后 p1++, p2++；。

第一步，交換 abc 和 def ，
abc defghi->def abcghi

第二步，交換 abc 和 ghi，
def abcghi->def ghiabc

整個過程，看起來，就是 abc 一步一步 向后移動
abc defghi
def abcghi
def ghi abc

這個有個限制，如果字符串的個數正好是平移位的整數倍還好，如果不是 的話還要進行調整：

由上述例子九個元素的序列 abcdefghi，您已經看到， m=3 時， p2 恰好指到了數組最后
一個元素，于是，上述思路沒有問題。 但如果上面例子中 i 的后面還有元素列?
即，如果是要左旋十個元素的序列： abcdefghij， ok，下面，就舉這個例子，對 abcdefghij
序列進行左旋轉操作：
如果 abcdef ghij 要變成 defghij abc：
abcdef ghij
1. def abc ghij
2. def ghi abc j //接下來， j 步步前移
3. def ghi ab jc
4. def ghi a j bc
5. def ghi j abc
下面，再針對上述過程，畫個圖清晰說明下，如下所示：

def ghi abc jk
當 p1 指向 a， p2 指向 j 時，由于 p2+m 越界，那么此時 p1， p2 不要變
這里 p1 之后（ abcjk)就是尾巴，處理尾巴只需將 j,k 移到 abc 之前，得到最終序列，代碼
編寫如下：

#include<iostream> #include<string> using namespace std; void rotate(string & str, int m) {if(str.length() == 0 || m <= 0)return;int n = str.length();if (m%n <= 0)return;int p1 = 0, p2 = m;int k = (n - m) - n%m;//表示可以平移的位數while (k--){swap(str[p1], str[p2]);p1++;p2++;}//表示平移到了界限出 就是后面的字符串的個數不夠平移的位數 //下面考慮怎么設置吧剩余的字符串 進行平移int r = n - p2;while (r--){int i = p2;while (i > p1){swap(str[i], str[i - 1]);i--;}p2++;p1++;} } int main() {string ch = "abcdefghijk";rotate(ch, 3);cout<<ch << endl;system("pause");return 0; }

總結

以上是生活随笔為你收集整理的程序员编程艺术第一章（第二节）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。