建设部信访网站/百度广告联盟一个月能赚多少

前言

题目：151. 翻转字符串里的单词

参考题解：翻转字符串里的单词-力扣官方题解

提交代码

使用栈翻转

使用空格作为分隔符，提取语句中的单词放入栈中。将栈中的单词弹出，连接成语句。从而翻转语句。

class Solution {
public:string reverseWords(string s) {istringstream ss(s);stack<string> st;string result;// 当一句话中的单词全部压栈string word;while(ss>>word){st.push(word);st.push(" "); // 压入一个空格}st.pop();// 弹栈到result中while(!st.empty()){result+=st.top();st.pop();}return result;}
};

原空间翻转

除非脑力过剩，要不然不会使用这种方法。不使用附加空间进行翻转，我参看了答案的思路之后，也进行了代码实现。

思路：移除多余空格-将整个字符串反转-将每个单词反转。

class Solution {
public:string deleteExtraSpaces(string s){// 使用快慢指针删除字符串中的多余空格：[i,j)范围的内容为多余内容if(s.empty())return s;const int len = s.size();int i=0,j=0;while(j<len){if((s[j]!=' ') || (j-1>=0 && s[j-1]!=' ')) // 合法需要保留的字符("word ")：本身不是空格 || 作为分隔符的空格(本身是空格 && 前一个不是空格)s[i++] = s[j++]; else{j++;}}if(s[i-1]==' ') // 上面过滤出的是(word )*格式。过滤，最后一个可能是空格，单独处理一下i--;assert(s[0]!=' ' || s[len-1]!=' ');if(i!=len)s.resize(i);return s;}// string reverseWord(string s, int start, int end){ //[start，end]闭区间翻转//     reverse(s.begin()+start,s.begin()+end+1);// }string reverseWords(string s) {if(s.empty())return s;s = deleteExtraSpaces(s); // 删除多余空格reverse(s.begin(),s.end()); // 字符串翻转// 翻转单词,[i,j]闭合范围内为一单词int i=0,j=0;s.push_back(' '); // 统一格式为(word )const int len = s.size();while(i<len && j<len){while(s[j]!=' ') j++;reverse(s.begin()+i,s.begin()+j);i = j+1;j++; }s.pop_back(); // 删除最后一个空格return s;}
};

附录

关于删除字符串之前/之后的空格，我这里保存了一份挺好看的代码。

// trim from start (construct new string)
inline std::string ltrim(const std::string &str){std::string s(str);s.erase(s.begin(), std::find_if_not<decltype(s.begin()), int(int)>(s.begin(), s.end(),std::isspace));return s;}// trim from end (construct new string)
inline std::string rtrim(const std::string &str){std::string s(str);s.erase(std::find_if_not<decltype(s.rbegin()), int(int)>(s.rbegin(), s.rend(),std::isspace).base(), s.end());return s;
}