算法刷题-字符串-151.反转单词

题目

给一串字符串，里面有若干单词，以空格界定单词的结束，翻转其中的单词

输入：s = " hello world "
输出：“world hello”

需要注意的是，给定的字符串可能存在头空格、尾空格以及中间的空格数量不唯一的情况。

要点

因为有多余空格的存在，所以如果普通的处理遍历，需要创建一个新的string存放，并需要考虑去掉开头结尾以及中间重复空格的情况，需要注意多个条件
那么如果就在原始字符串上面修改的话，也还是要注意条件，这会就可以先去除多余空格，再翻转整个字符，再逐个翻转单词。

代码（O(1)版，在原始字符串上处理）

步骤就是先去掉所有多余空格，再反转整个字符串，再逐个单词内部进行反转到正确顺序

class Solution {
public:void removeEmpty(string &s) {int slow = 0, fast = 0;for (;fast < s.size(); fast++) {if (s[fast] != ' ') { //当fast遍历到字母开始操作if (slow > 0) s[slow++] = ' '; //当不是第一个单词的时候，手动添加一个空格while(s[fast] != ' ' && fast < s.size()) { //这里就是当fast遇到单词的时候，赋值给slow，直到这个单词结束s[slow++] = s[fast++];}}}s.resize(slow); //这里直接slow而不是slow+1是因为最后while还给slow++了}void reverseString(string &s, int head, int end) {while (head < end) {swap (s[head], s[end]);head++;end--;}}
//这个是实际运行的成员函数string reverseWords(string s) {removeEmpty(s); //去重空格，定义在上面 reverseString(s, 0, s.size()-1); //反转字符串，定义在上面//对逐个单词内部逐个反转for (int start = 0, end = 0; end <= s.size(); end++) { //注意这里end终止的条件为什么是<=size()//是因为需要有一个判断最后一个单词结束的标志，相当于一个空格一样，而这个s.size()就是这个标志if (s[end] == ' ' || end == s.size()) {reverseString(s, start, end-1);start = end + 1;}}return s;}
};

代码（O(N)版，需要注意的是判断条件

class Solution {
public:string reverseWords(string s) {string result = "";// auto it = s.end()-1;// string::iterator start1;// string::iterator end = s.end()-1;int count = 0;int pos = s.size()-1;int start = 0;while (pos >= 0) {if(s[pos] == ' ') { //当遇到' '开始处理，if(count != 0) { //如果count！=0,证明遇到的' '是一个单词的结尾标志，就进行如下处理start = pos + 1;result.append(s, start, count);result += " ";}count = 0; //反正遇到了' '就让count=0}else { //如果没遇到' '，就让count++count++;}pos--;}if (count > 0) { //这里当遍历完之后，因为开头可能没有' '用来标志第一个单词的结束，这里手动添加result.append(s, pos+1, count);} else { //要么就是开头有多余空格，上面的while循环里会多给它加个''就删除result.erase(result.size()-1,1); //删除空格}return result;}
};