面试题42：反转单词顺序 VS 左旋转字符串

题目一：输入一个英文句子，反转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串”I am a student.”，则输出”student. a am I”。

分析

解法如下：

1. 先将整个字符串翻转；
2. 将每个单词翻转(以空格分隔)。

代码如下：

void ReverseSentence(string str)
{
    int i,j,tmp;
    for(i=0,j=str.size()-1;i<j;++i,--j)
    {
        swap(str[i],str[j]);
    }
    for(i=0;i<str.size();)
    {
        j=i;
        while(j<str.size() && str[j]!=' ')
            j++;
        tmp=j;
        j--;
        for(;i<j;++i,--j)
            swap(str[i],str[j]);
        while(tmp<str.size() && str[tmp]==' ')
            tmp++;
        i=tmp;
    }
}

题目二：字符串的左旋操作时把字符串的前面若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋操作的功能。比如输入字符串”abcdefg”和数字2，改函数将返回左旋2位得到的结果”cdefgab”。

分析

由上一道题目我们可以得知，将字符串翻转一次会将单词的顺序也给翻转了。所以我们还需要在将每个单词翻转一次。这题目也一样，我们可以将”abcdefg”的前2位和后5位看成两个单词(只不过不是以空格分隔而已)，也翻转两次即可。

代码如下：

void LeftRotateString(string& str,int n){
    if(n<=0)
        return;
    n%=str.size();
    int i,j;
    for(i=0,j=str.size()-1;i<j;++i,--j)
        swap(str[i],str[j]);
    i=0,j=str.size()-n-1;
    while(i<j)
        swap(str[i++],str[j--]);
    i=str.size()-n,j=str.size()-1;
    while(i<j)
        swap(str[i++],str[j--]);
}

以上

如果你有任何想法或是可以改进的地方，欢迎和我交流！

完整代码及测试用例在github上：点我前往(题目一)  点我前往(题目二)