剑指 Offer 58 - I. 翻转单词顺序
</br></br>
题目：
输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输出"student. a am I"。
示例1：
输入: "the sky is blue"
输出: "blue is sky the"
示例2：
输入: " hello world! "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例3：
输入: "a good example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
说明：
无空格字符构成一个单词。
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
</br></br>
思路一：
逆序双指针
1.用
n记录当前字符串长度，再开辟一个新的字符串str用来存放逆序遍历到的单词；2.逆序遍历，当字符不为空格时，使用
right记录下当前i的位置，然后i--向前查找下一个空格，当s[i] == ' '时，可以通过right - i得到当前单词的长度，i + 1得到单词的首字母，通过substr函数将该单词放到新的字符串str中；3.当我们逆序遍历完成之后，得到新的字符串，此时
str已经是原来字符串翻转后形成的，但是要注意的是，使用str += s.substr(i + 1, right - i) + " "向str中追加最后一个单词时，空格也被放到了里面，所以要单独对最后一个空格进行处理；
可以使用
substr函数进行处理即return str.substr(0,str.size() - 1)；也可以使用
erase函数删除最后一个空格，但是此时要判断str是否为空字符串，避免erase时数组越界；还可以使用
pop_back函数直接尾删掉最后一个字符。我们以字符串
we are family为例，头部两个空格，are和family中间三个空格，尾部三个空格。具体过程可参考下图：
代码如下：
class Solution {
public:
string reverseWords(string s) {
int n = s.size();
string str;//string类默认值为空
//从结尾开始向前遍历，这样的话不用翻转，单词顺序直接就是翻转后的
for(int i = n - 1; i >= 0; i--)
{
//当s[i]不为空时，追加到新字符串
if(s[i] != ' ')
{
int right = i;//记录此时i的位置
while( i >= 0 && s[i] != ' ' ) //要注意这里条件的先后顺序
{
i--;
}
//right - i 计算的是字符长度
//s[i]此时为空格，i+1就是单词的首个字符
str += s.substr(i + 1, right - i) + " ";
}
}
//最后这里的str字符串最后一个元素为空格
// 1. return str.substr(0,str.size() - 1);
//3. str.pop_back();
// return str;
//2.
if(str == "") //还要考虑当字符串为空的情况
return str;
str.erase(str.size() - 1, 1);
return str;
}
};
时间复杂度：
O(N)空间复杂度：
O(N)
</br></br>
思路二：
通过三个指针对原子符串进行修改从而实现翻转单词顺序。
1.先将整个字符串翻转；
2.设置一个变量
idx用来将单词从头开始填入字符串，设置变量start从头开始找，当s[start] != ' '时，说明此时为单词的头部，向后遍历，当s[end] != ' '时找到单词结尾，通过reverse(s.begin() + idx - (end -start), s.begin() + idx);对单词进行翻转；3.
start = end;更新start，并找下一个单词……当idx != 0时说明已经插入了单词需要添加空格s[idx++] = ' '；4.当字符串中单词找完，即循环结束之后，
s.erase(s.begin() + idx,s.end());删除idx开始的往后的字符，因为原字符串中的单词已经通过循环放到了前面。我们以字符串
we are family为例，头部两个空格，are和family中间三个空格，尾部三个空格。具体过程可参考下图：
代码如下：
class Solution {
public:
string reverseWords(string s) {
//直接翻转整个字符串
reverse(s.begin(),s.end());
int n = s.size();
int idx = 0; //用来记录单词和给空格
for(int start = 0; start < n; start++)
{
//当s[start]不等于空格时记录单词
if(s[start] != ' ')
{
//当idx不等于0时，说明此时字符串已经完成了一个单词的写入，所以要加上空格
if(idx != 0)
s[idx++] = ' ';
//开始向后遍历，找到单词的结尾
int end = start;
while(end < n && s[end] != ' ')
s[idx++] = s[end++];
//单词写入之后对这个单词进行翻转
reverse(s.begin() + idx - (end -start), s.begin() + idx);
//再更新start,找下一个单词
start = end;
}
}
//将从idx开始的往后的字符全部删除
s.erase(s.begin() + idx,s.end());
return s;
}
};
【文章原创作者：欧洲服务器 http://www.558idc.com/helan.html 复制请保留原URL】时间复杂度：
O(N)空间复杂度：
O(1)