题目描述：
牛客最近来了一个新员工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<len;++i) { int j=i; // 寻找空格位置 while(j<len&&str[j]!=' ') j++; // 将子串放入栈 string ss=str.substr(i,j-i); s.push(ss); i=j; } // 栈依次弹出 int size=s.size(); for(int i=0;i<size;++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; } };
