反转字符串中的单词
双指针
左指针在单词第一位，右指针在单纯结束后一位，抽取子串，头插入到result
class Solution { public: string reverseWords(string s) { int left=0 ,right=1; string result , temp; if(s.size()==1) return s;//针对单一字母 while( left < right && right<s.size() )//找到左指针位置，单词第一个字母处 { while(s[left]==' ') { left++; right++; if(right > s.size()) %应对单词后面多个空格没有新单词，类似“abc ” { result.erase(result.size()-1,1); return result; } } while(s[right]!=' '&& s[right]!='\0')//确定右指针位置，在单词最后一个字母后 { right++; } temp = s.substr(left,right-left);//抽取子串 temp +=' ';//添加空格 result.insert(0, temp);//头插字串 left = right; right= left+1; } result.erase(result.size()-1,1);//去除最后一个空格 return result; } };
低空间复杂度，反转库函数
首先去除多余空格，之后整个字符串反转，最后每个单词反转
class Solution { public: string reverseWords(string s) { int left=0 , right=0; //去除多余的空格 while(right < s.size()) { if(left==0 && s[right] ==' ') { right++; } else if(left != 0 && s[right-1] ==' '&&s[right] ==' ') { right++; }else { s[left] = s[right]; left++; right++; } } if(s[left-1]==' ')left--;//针对最后一个是空格 s.resize(left); //反转字符串 reverse(s.begin(),s.end()); //反转单词 left=0 , right=0; while(right <= s.size()) { while(s[right] != ' '&& right<s.size()) right++; reverse(s.begin() + left, s.begin() + right); left = right+1; right=left+1; } return s; } };
低空间复杂度，无库函数
class Solution { public: void reverse(string& s, int start, int end){ //翻转，区间写法：左闭又闭 [] for (int i = start, j = end; i < j; i++, j--) { swap(s[i], s[j]); } } void removeExtraSpaces(string& s) {//去除所有空格并在相邻单词之间添加空格, 快慢指针。 int slow = 0; //整体思想参考https://programmercarl.com/0027.移除元素.html for (int i = 0; i < s.size(); ++i) { // if (s[i] != ' ') { //遇到非空格就处理，即删除所有空格。 if (slow != 0) s[slow++] = ' '; //手动控制空格，给单词之间添加空格。slow != 0说明不是第一个单词，需要在单词前添加空格。 while (i < s.size() && s[i] != ' ') { //补上该单词，遇到空格说明单词结束。 s[slow++] = s[i++]; } } } s.resize(slow); //slow的大小即为去除多余空格后的大小。 } string reverseWords(string s) { removeExtraSpaces(s); //去除多余空格，保证单词之间之只有一个空格，且字符串首尾没空格。 reverse(s, 0, s.size() - 1); int start = 0; //removeExtraSpaces后保证第一个单词的开始下标一定是0。 for (int i = 0; i <= s.size(); ++i) { if (i == s.size() || s[i] == ' ') { //到达空格或者串尾，说明一个单词结束。进行翻转。 reverse(s, start, i - 1); //翻转，注意是左闭右闭 []的翻转。 start = i + 1; //更新下一个单词的开始下标start } } return s; } };
二刷
class Solution { public: string reser(string &s , int left ,int right) { int left_tmp = left , right_tmp = right; while(left < right) { char tmp = s[right]; s[right] = s[left]; s[left] = tmp; left++; right--; } string s1(s.begin()+left_tmp , s.begin()+right_tmp+1); return s1; } string reverseWords(string s) { string result; reverse(s.begin(),s.end()); for(int left =0 ; left<s.size() ; left++) { if(s[left] == ' ') continue; for(int right = left ; right<s.size() ;right++) { if(right==s.size()-1 || s[right+1]==' ') { result += reser(s,left,right); result += ' '; left = right; break; } } } result.erase(result.size()-1,1); return result; } };
