双指针 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;
}
};