一年没有管理博客园了，说来实在惭愧。。
最近开始刷LeetCode，之前没刷过，说来也实在惭愧。。。
刚开始按 AC Rates 从简单到难刷，觉得略无聊，就决定按 Add Date 刷，以后也可能看心情随便选题…(⊙o⊙)…今天做了14年 Add 的三个题，其中 Maximum Product Subarray 着实把我折腾了好一会儿，所以想想还是跟大家分享一下我的解法，也或许有更好的方法，期待大家的分享。就把三个题按 Add Date 的先后顺序分享一下吧。
Add Date 2014-03-05
Given an input string, reverse the string word by word.
For example,
Given s = "the sky is blue",
return "blue is sky the".
Clarification:
- What constitutes a word?
A sequence of non-space characters constitutes a word. - Could the input string contain leading or trailing spaces?
Yes. However, your reversed string should not contain leading or trailing spaces. - How about multiple spaces between two words?
Reduce them to a single space in the reversed string.
单纯把 "the sky is blue" reverse 成 "blue is sky the" 是件很容易的事情，也是比较经典的题目，不过本题说：
1. s 中的开头和结尾有可能有空格，reverse 后的 string 中要去掉；
2. 连续多个空格要变成一个空格。
我的 code 略折腾，用了两个函数：
1. reverseWord 实现最基本的 reverse，首先整个 reverse，变为“eulb si yks eht”，然后每个 word reverse，遍历两边即可。
2. removeSpace 实现检查和删除空格。遍历一遍即可。
复杂度O(n).
附 code，仅供参考。
class Solution {
public:
void reverseWord(string &s) { //反转字符串
string::iterator pre = s.begin();
string::iterator post = s.end()-;
char tmp;
while(pre < post) { //反转整个字符串
tmp = *pre;
*pre = *post;
*post = tmp;
++pre;
--post;
}
pre = s.begin();
post = pre;
while(post != s.end()) { //反转每个单词
while(pre != s.end() && *pre == ' ') {
++pre;
}
if(pre == s.end())
return;
post = pre;
while(post != s.end() && *post != ' ') {
++post;
}
--post;
if(post != s.end() && pre < post) {
string::iterator p1 = pre;
string::iterator p2 = post;
while(p1 < p2) {
tmp = *p1;
*p1 = *p2;
*p2 = tmp;
++p1;
--p2;
}
}
++post;
pre = post;
}
}
void removeSpace(string &s) { //检查和删除空格
string::iterator pre = s.begin();
string::iterator post = pre;
while(pre != s.end() && *pre == ' ') { //删除开头的空格
s.erase(s.begin());
pre = s.begin();
}
if(pre == s.end())
return;
post = pre;
while(post != s.end()) { //把连续多个空格变为一个
while(pre != s.end() && *pre != ' ')
++pre;
if(pre == s.end())
return;
post = pre+;
while(post != s.end() && *post == ' ') {
s.erase(post);
post = pre+;
}
++pre;
}
if(!s.empty()) { //如果最后有空格则删除
pre = s.end()-;
if(*pre == ' ')
s.erase(pre);
}
}
void reverseWords(string &s) {
reverseWord(s);
removeSpace(s);
}
};