题目描述：
给定一个字符串，要求将字符串前面的若干个字符移到字符串的末尾。例如 ：
讲字符串“abcdef”的前3个字符'a','b'和'c'移动到字符串的尾部，那么原字符串将变成"defabc"。
分析与解法
一、【暴力翻转】每次右移一位，移动n次
说明：长度为m字符串的字符串，假设需要移动次数为n，总共需要mn次操作，时间复杂度为O(mn)，空间复杂度为O(1)
void LeftShiftOne(char *cStr, int iLen)
{
char cTmp = cStr[0];
for (int i = 1; i < iLen; ++i) {
cStr[i-1] = cStr[i];
}
cStr[iLen-1] = cTmp;
}
void LeftRotateString(char *str, int n)
{
int strLne = strlen(str);
for (int i = 0; i < n; i++) {
LeftShiftOne(str, strLne);
}
}
二、【三步翻转】
用字符串”abcdef“举例
1、将原字符串分为X和Y两个部分，其中X为”abc“， Y为”def“
2、将X的所有字符翻转，由”abc“得到”cba“，将Y的所有字符翻转，由”def“得到“fed”
3、将上面得到的整个字符串翻转，由”cbafed“得到“defabc”
说明：时间复杂度为O(n)，空间复杂度为O(1)
/*
* iFrom:翻转的起始坐标
* iTo:翻转的终止坐标
*/
void ReverseString(char *cStr, int iFrom, int iTo)
{
char cTmp;
while (iFrom <= iTo)
{
cTmp = cStr[iFrom];
cStr[iFrom++] = cStr[iTo];
cStr[iTo--] = cTmp;
}
}
void LeftRotateString(char *cStr, int n)
{
int istrLen = strlen(cStr) - 1;
ReverseString(cStr, 0, n-1);
ReverseString(cStr, n, istrLen);
ReverseString(cStr, 0, istrLen);
}
题目拓展：单词翻转
输入一个英文句子，翻转句子中单词的顺序。要求单词内字符的顺序不变，句子中单词以空格符隔开。为简单起见，标点符号和普通字母一样处理。例如若输出“I am a student,”，则输出“student. a am i”
解法同上述的三步翻转
/*
* iFrom:翻转的起始坐标
* iTo:翻转的终止坐标
*/
void ReverseString(char *cStr, int iFrom, int iTo)
{
char cTmp;
while (iFrom <= iTo)
{
cTmp = cStr[iFrom];
cStr[iFrom++] = cStr[iTo];
cStr[iTo--] = cTmp;
}
}
void RotateString(char *cStr)
{
int iStart = 0, iEnd = 0;
while(cStr[iEnd])
{
// 跳过空格，找到要反转的第一个字符
while(cStr[iEnd] && cStr[iEnd] == ' ')
{
iEnd++;
}
iStart = iEnd;
// 跳转到要翻转的字符结尾
while(cStr[iEnd] && cStr[iEnd] != ' ') {
iEnd++;
}
ReverseString(cStr, iStart, iEnd-1);
iEnd++;
}
ReverseString(cStr, 0, iEnd-2);
}
