题目:定义字符串的左旋转操作:把字符串前面的若干个字符移动到字符串的尾部。如把字符串abcdef左旋转2位得到字符串cdefab。请实现字符串左旋转的函数。要求时间对长度为n的字符串操作的复杂度为O(n),辅助内存为O(1)。
把一个字符串逆序,空间复杂度是1,
我们还是把字符串看成有两段组成的,记位XY。左旋转相当于要把字符串XY变成YX。我们先在字符串上定义一种翻转的操作,就是翻转字符串中字符的先后顺序。把X翻转后记为XT。显然有(XT)T=X。
我们首先对X和Y两段分别进行翻转操作,这样就能得到XTYT。接着再对XTYT进行翻转操作,得到(XTYT)T=(YT)T(XT)T=YX。正好是我们期待的结果。
分析到这里我们再回到原来的题目。我们要做的仅仅是把字符串分成两段,第一段为前面m个字符,其余的字符分到第二段。再定义一个翻转字符串的函数,按照前面的步骤翻转三次就行了。时间复杂度和空间复杂度都合乎要求。
参考代码如下:
#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<int>(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 --;
}
}
}
分享到:
相关推荐
程序员面试题精选100题
程序员面试题精选100题
程序员面试题精选程序员面试题精选程序员面试题程序员面试题精选精选
程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试...
程序员面试题精选100题-何海涛 程序员 面试题 算法 数据结构
程序员面试题精选100题(2008)程序员面试题精选100题(2008)
程序员面试题精选100题
一份可以让大家在求职时更能自信的题解,经典的100题,让大家可以感受到算法的经典,当然,自己要更加努力,要懂得举一反三才能更上一层楼!
程序员面试题精选100题
程序员面试题精选100题,以前下过的不全,自己在网上搜了搜,整理了一下。
------------------------------------- java程序员早期面试题汇总 BAT经典面试题汇总.pdf Java常考面试题.pdf java面试题(题库全)....程序员面试题精选100题.pdf ... -------------------------------------