双指针 Leetcode 151 反转字符串中的单词

Leetcode 151

学习记录自代码随想录

法一：利用额外空间

class Solution {
public:string reverseWords(string s) {istringstream iss(s);vector<string> words_string;string k;while(iss >> k){words_string.push_back(k);}string res;for(int i = words_string.size()-1; i >= 0; i--){res += words_string[i];if(i != 0) res += " ";}return res;}
};

法二：原地改变字符串，不利用额外空间

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 removeadditionblack(string& s){int slow = 0, fast = 0;// 去除开头空格while(s.size() > 0 && fast < s.size() && s[fast] == ' '){fast++;}// 去除中间空格while(s.size() > 0 && fast < s.size()){if(fast > 1 && s[fast] == s[fast-1] && s[fast] == ' '){fast++;}else{s[slow++] = s[fast++];}}// 去除结尾空格if(slow > 1 && s[slow-1] == ' '){s.resize(slow-1);}else{s.resize(slow);}}string reverseWords(string s){// 三步：1.去除多余空格removeadditionblack(s);// 2.整个字符串反转reverse(s, 0, s.size()-1);// 3.单个单词反转int cnt = 0;// 注意有等于号for(int i = 0; i <= s.size(); i++){if(s[i] == ' ' || i == s.size()){reverse(s, i-cnt, i-1);cnt = 0;}else{cnt++;}}return s;}
};