左旋轉(zhuǎn)字符串

　　題目：定義字符串的左旋轉(zhuǎn)操作：把字符串前面的若干個字符移動到字符串的尾部。如把字符串a(chǎn)bcdef左旋轉(zhuǎn)2位得到字符串cdefab。請實現(xiàn)字符串左旋轉(zhuǎn)的函數(shù)。要求時間對長度為n的字符串操作的復(fù)雜度為O(n)，輔助內(nèi)存為O(1)。

　　分析：如果不考慮時間和空間復(fù)雜度的限制，最簡單的方法莫過于把這道題看成是把字符串分成前后兩部分，通過旋轉(zhuǎn)操作把這兩個部分交換位置。于是我們可以新開辟一塊長度為n+1的輔助空間，把原字符串后半部分拷貝到新空間的前半部分，在把原字符串的前半部分拷貝到新空間的后半部分。不難看出，這種思路的時間復(fù)雜度是O(n)，需要的輔助空間也是O(n)。

　　接下來的一種思路可能要稍微麻煩一點。我們假設(shè)把字符串左旋轉(zhuǎn)m位。于是我們先把第0個字符保存起來，把第m個字符放到第0個的位置，在把第2m個字符放到第m個的位置…依次類推，一直移動到最后一個可以移動字符，最后在把原來的第0個字符放到剛才移動的位置上。接著把第1個字符保存起來，把第m+1個元素移動到第1個位置…重復(fù)前面處理第0個字符的步驟，直到處理完前面的m個字符。

　　該思路還是比較容易理解，但當(dāng)字符串的長度n不是m的整數(shù)倍的時候，寫程序會有些麻煩，感興趣的朋友可以自己試一下。由于下面還要介紹更好的方法，這種思路的代碼我就不提供了。

　　我們還是把字符串看成有兩段組成的，記位XY。左旋轉(zhuǎn)相當(dāng)于要把字符串XY變成YX。我們先在字符串上定義一種翻轉(zhuǎn)的操作，就是翻轉(zhuǎn)字符串中字符的先后順序。把X翻轉(zhuǎn)后記為XT。顯然有(XT)T=X。

　　我們首先對X和Y兩段分別進(jìn)行翻轉(zhuǎn)操作，這樣就能得到XTYT。接著再對XTYT進(jìn)行翻轉(zhuǎn)操作，得到(XTYT)T=(YT)T(XT)T=YX。正好是我們期待的結(jié)果。

　　分析到這里我們再回到原來的題目。我們要做的僅僅是把字符串分成兩段，第一段為前面m個字符，其余的字符分到第二段。再定義一個翻轉(zhuǎn)字符串的函數(shù)，按照前面的步驟翻轉(zhuǎn)三次就行了。時間復(fù)雜度和空間復(fù)雜度都合乎要求。

　　參考代碼如下：

　　#include "string.h"

　　///////////////////////////////////////////////////////////////////////

　　// Move the first n chars in a string to its end

　　///////////////////////////////////////////////////////////////////////

　　char* LeftRotateString(char* pStr, unsigned int n)

　　{

　　if(pStr != NULL)

　　{

　　int nLength = static_cast(strlen(pStr));

　　if(nLength > 0 || n == 0 || n > nLength)

　　{

　　char* pFirstStart = pStr;

　　char* pFirstEnd = pStr + n - 1;

　　char* pSecondStart = pStr + n;

　　char* pSecondEnd = pStr + nLength - 1;

　　// reverse the first part of the string

　　ReverseString(pFirstStart, pFirstEnd);

　　// reverse the second part of the strint

　　ReverseString(pSecondStart, pSecondEnd);

　　// reverse the whole string

　　ReverseString(pFirstStart, pSecondEnd);

　　}

　　}

　　return pStr;

　　}

　　///////////////////////////////////////////////////////////////////////

　　// Reverse the string between pStart and pEnd

　　///////////////////////////////////////////////////////////////////////

　　void ReverseString(char* pStart, char* pEnd)

　　{

　　if(pStart == NULL || pEnd == NULL)

　　{

　　while(pStart <= pEnd)

　　{

　　char temp = *pStart;

　　*pStart = *pEnd;

　　*pEnd = temp;

　　pStart ++;

　　pEnd --;

　　}

　　}

　　}

　　相關(guān)推薦：

　　2015年軟考信息技術(shù)處理員考前知識點總結(jié)匯總

　　2015年軟件水平考試《程序員》提高練習(xí)題匯總

　　2015軟件水平考試《程序員》知識點總結(jié)匯總