【題目】左旋轉字元串。把字元串前面的若幹個字元移動到字元串的尾部。如把字元串abcdef左旋轉 3位得到字元串 defabc。請實作字元串左旋轉的函數。要求時間對長度為n 的字元串操作的複雜度為O(n)，輔助記憶體為O(1)。
【思路】方法1：要求了時間和空間複雜度，從字元特征上看，可以認為，後面的字元往前移動了幾位。可以一次往前移動一位，移動的次數就是要求旋轉的次數，時間複雜度是小于n的，空間上采用memmove()函數調整記憶體内容。方法2：把字元串看成有兩段組成的，記位XY。左旋轉相當于要把字元串XY 變成YX。先在字元串上定義一種翻轉的操作，就是翻轉字元串中字元的先後順序。把 X翻轉後記為XT。顯然有(XT)T=X。首先對X和 Y兩段分别進行翻轉操作，這樣就能得到 XTYT。接着再對XTYT 進行翻轉操作，得到(XTYT)T=(YT)T(XT)T=YX。正好是期待的結果。
【代碼】 //By proing [http://blog.csdn.net/proing] #include "stdafx.h" #include #include #include using namespace std; int LeftRotate(char *str,int lnum) { if(NULL == str) return 0; char temp = NULL; int len = strlen(str); if(len <= lnum || lnum < 1) return 0; for(int i= 0 ;i <lnum;i++) { temp = *(str+lnum-1-i); memmove( str+lnum-i-1, str+lnum-i,len-lnum); *(str+len-i-1) = temp; } return 1; }