剑指offer(C++)-JZ73：翻转单词序列(数据结构-队列 & 栈)

作者：翟天保Steven
版权声明：著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处

题目描述：

牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“nowcoder. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a nowcoder.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？

数据范围：1≤n≤100 
进阶：空间复杂度 O(n)  ，时间复杂度 O(n)  ，保证没有只包含空格的字符串

示例：

输入：

"nowcoder. a am I"

返回值：

"I am a nowcoder."

解题思路：

本题考察数据结构队列 & 栈的使用。两种解法：

1）利用栈先进后出特性。遍历字符串，拆分各个子串放入栈；遍历栈，依次弹出。注意除了最后一个子串，其他的子串都要带一个空格。

2）利用STL库reverse翻转函数。先整体翻转一次，再遍历确定各个子串，对子串进行二次翻转。

测试代码：

解法一：栈

class Solution {
public:
    string ReverseSentence(string str) {
        string result;
        int len=str.length();
        
        // 使用栈：先进后出
        // 依次放入
        stack<string> s;
        for(int i=0;i
        {
            int j=i;
            // 寻找空格位置
            while(j' ')
                j++;
            // 将子串放入栈
            string ss=str.substr(i,j-i);
            s.push(ss);
            i=j;
        }
        
        // 栈依次弹出
        int size=s.size();
        for(int i=0;i
        {
            result+=s.top();
            // 最后一个子串不加空格
            if(i!=(size-1))
                result+=" ";
            s.pop();
        }
        
        return result;
    }
};

解法二：reverse翻转

class Solution {
public:
    string ReverseSentence(string str) {
        int len = str.length();
 
        // 先整体反转
        reverse(str.begin(), str.end()); 
 
        // 各个子串再次翻转
        for(int i = 0; i < len; ++i)
        {
            int j = i;
 
            //以空格为界找到一个单词
            while(j < len && str[j] != ' ') 
                j++;
 
            //将这个子串翻转
            reverse(str.begin() + i, str.begin() + j); 
 
            i = j;
        }
 
        return str;
    }
};

---

祝大家情人节快乐！