题解 | #翻转单词序列#

翻转单词序列：最直观的想法是，首先分割单词，然后再按照顺序拼接成字符串。该题较为容易处理的地方在于，其测试字符串是严格意义上的各个单词之间只间隔一个空格，且字符串头部和尾部以及单词与单词之间没有多余的空格，这使得分割单词与拼接字符串的处理变得容易许多。分割单词是使用的双指针，使用变量start记录当前单词起始位置，使用变量end记录当前单词结束位置，其初始化为字符串的结束位置，然后从后向前遍历字符串，如果当前字符不为空格而当前字符的前一个字符为空格，则表明出现单词分割，更新当前单词起始位置start并截取[start,end]加入结果字符串res中，然后再更新下一个单词的结束位置end，依次类推，最后将当前单词的起始位置更新为字符串的起始位置并单独截取起始部分，最后返回res即可。(到目前为止没找到一种优雅写法)

// 严格各个单词间隔一个空格
string ReverseSentence(string str) 
{
    // 空串特殊处理
    if(str=="")
       return str;
    // 结果字符串
    string res;
    // 记录起始位置
    int start=0;
    // 记录结束位置
    int end=0;
    // 从后向前遍历字符串
    int i=str.size()-1;
    // 单词结束位置
    end=i;
    for(;i-1>=0;i--)
    {
        // 单词分割
        if(str[i]!=' '&&str[i-1]==' ')
        {
            // 单词起始位置
            start=i;
            // 加入结果
            res+=str.substr(start,end-start+1)+' ';
            // 下一个单词结束位置
            end=i-2;           
        }
    }
    // 起始单独处理
    start=i;
    res+=str.substr(start,end-start+1);
    return res;
}

优化：上述方法我们使用了一个新的字符串res来保存结果，那么能不能直接原地实现呢？当然可以！两次反转！即首先整体反转字符串，但是这样会改变单词顺序，所以我们还需要标记单词起始位置和结束位置，然后再单独反转每一个单词，这样既实现了反转又保持了单词的相对顺序，同时还不用处理空格喔！reverse可以在原字符串的基础上反转区间字符串喔！（还不错！遇到字符串！遇到反转！多想想多次反转！）

// 严格各个单词间隔一个空格
string ReverseSentence(string str) 
{
    // 空串特殊处理
    if(str=="")
       return str;
    // 记录字符串长度
    int n=str.size();
    reverse(str.begin(),str.end());
    for(int i=0;i<n;i++)
    {
        int j=i;
        // 以空格为界找到一个单词
        while(j<n&&str[j]!=' ')
            j++;
        // 反转单词 i表示起始位置 j表示结束位置
        reverse(str.begin()+i,str.begin()+j);
        // 重置起始位置 j为空格 下一轮循环i会再加一次
        i=j;
    }
    return str;
}