LeetCode 151. 翻转字符串里的单词-stringstream+双指针算法
原题链接
中等
作者:
bruce
,
2021-01-01 16:14:06
,
所有人可见
,
阅读 341
/**
* 方法 1,基于字符串流的操作sstream
*/
string reverseWords1(string &s)
{
istringstream iss(s);
string temp;
iss >> s;
cout << endl;
while (iss >> temp)
s = temp + " " + s;
if (!s.empty() && s[0] == ' ')
s = ""; //输入是空格的时候,输出为空
return s;
}
/**
* 方法 3,首先对每一个字符进行翻转,然后在对每个单词进行翻转即可
* 比如s="hello world",翻转每个字符,"dlrow olleh",接着翻转每个单词"world hello"完成
* 用双指针算法来做
*/
string reverseWords3(string s)
{
if (s.empty())
return s;
int n = s.size(), start = 0; // start用来记录当前非空的单词的起始位置
for (int i = 0; i < n; i++) // 遍历每个单词
{
if (s[i] == ' ')
continue;
int j = i, t = start; // t指向非空单词的起始位置
while (j < s.size() && s[j] != ' ') // 把空格的地方用单词向前平移
s[t++] = s[j++];
reverse(s.begin() + start, s.begin() + t); // 翻转这个单词
s[t++] = ' '; // 这个单词的下一位加一个空格
start = t, i = j; // 下一个单词的开始位置为当前的t,j赋值给i
}
if (start) // 最后的起始位置不为空,那么最后一位空格减去
start--;
s.erase(s.begin() + start, s.end());
reverse(s.begin(), s.end());
return s;
}