双指针应用四：翻转字符串里的单词
2021-05-08 本文已影响0人
程一刀
题目地址 https://leetcode-cn.com/problems/reverse-words-in-a-string/
题目描述 给定一个字符串，逐个翻转字符串中的每个单词。
示例 1： 输入: "the sky is blue" 输出: "blue is sky the"
示例 2： 输入: " hello world! " 输出: "world! hello" 解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3： 输入: "a good example" 输出: "example good a" 解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
参考代码
#include <iostream>
using namespace::std;
class Solution {
///字符串翻转
void reverse(string &str,int begin ,int end){
for (int i = begin,j = end; i<j; i++,j--) {
swap(str[i],str[j]);
}
}
/// 删 除 首尾 空格，多余空格
void deletespate(string &str) {
int begin = 0;
while (str[begin] == ' ' && begin < str.size()) {
begin ++;
}
int slow = 0;
for (;begin < str.size();begin ++) {
if (str[begin] == ' ' && str[slow -1 ] == ' ' && slow > 1) {
} else {
str[slow++] = str[begin];
}
}
if (str[slow - 1] == ' ' && slow >0) {
str.resize(slow-1);
} else {
str.resize(slow);
}
}
public:
string reverseWords(string s) {
deletespate(s);
reverse(s,0,s.size()-1);
int begin = 0;
int end = 0;
for (int i = 0; i< s.size(); i++) {
if (s[i] == ' ') {
end = i - 1;
reverse(s, begin, end);
begin = i+1;
} else {
}
}
// 反转最后个单词
reverse(s, begin, s.size()-1);
return s;
}
};
int main(int argc, const char * argv[]) {
// insert code here...
string str = " the sky is blue ";
string aa = Solution().reverseWords(str);
return 0;
}
