可以使用栈，将每个单词（字符串）压栈，然后弹栈就 OK 了
好吧，实际写下来考虑到可能存在的多余空格问题，代码看起来并不简介，而且写之前就很明显直到需要最差额外 n 的空间，时间复杂度最差 2n，所以都不算好
思路是压栈的时候只压单词本身，弹栈的时候再去拼空格
string reverseWords(string s) {
s += ' ';// 加一个空格避免需要额外清空temp
stack<string> stk;
string temp;
for (char ch : s) {
if (ch != ' ') temp += ch;
else if (!temp.empty()) {
stk.push(temp);
temp.clear();
}
}
int numOfWord = stk.size();
if (numOfWord == 0) return "";
for (int i = 0; i < numOfWord - 1; i++) {
temp = temp + stk.top() + ' ';
stk.pop();
}
return temp+stk.top();
}
需要额外注意栈空的情况，不然会指针越界
然后就是这种做法真的 时间/空间复杂度 都很差
string reverseWords(string s) {
string temp,res;
int notZero = 0;
while (s[notZero] == ' ') notZero++;
// 从后往前扫描，最后一位不能是0
for (int i = s.size() - 1; i >= notZero; i--) {
if (s[i] != ' ') temp.insert(temp.begin(),s[i]);
else if (!temp.empty()) {
res = res + temp + " ";
temp.clear();
}
}
return res+temp;
}
换一个思路，效率仍然很差，我觉得问题出在insert()之后每次的移动上面
最终思路我想应该是将每一个单词翻转，然后将整个字符串翻转
string reverseWords(string s) {
s += ' ';
int start = 0, end;
while (s[start] == ' ') s.erase(s.begin());
for (; start < s.size(); start++) {
if (s[start] != ' ') {
for (end = start + 1; end < s.size(); end++) {
if (s[end] == ' ') {
reverse(s.begin() + start, s.begin() + end);
start = end;
break;
}
}
}
}
reverse(s.begin(), s.end());// 至此完成翻转，接下来提取单词
start = 0;
while (s[start] == ' ') s.erase(s.begin());
// 删除中间多余空格
for (start = 0; start < s.size(); start++) {
if (s[start] == ' ' && (start + 1) < s.size()) {
while (s[start + 1] == ' ')s.erase(s.begin() + start + 1);
}
}
return s;
}
AC 代码，不能说是最完美的，但是应该足够完美了，有几个巧思
- s 一上来就追加一个
' '，这样可以保证挨个单词翻转的时候不用追加最后一步操作 - 翻转前删除头部所有空格，翻转后再删除一遍头部所有空格（其实就是没翻转前的尾空格），这样也删除了第一步自己追加的空格，这样做很省事也很见简单
另外就是原地操作数组需要格外注意指针越界的情况
string reverseWords(string s) {
int len = s.size();
int start = 0, end = 0;
bool wordStarted = false;
for (int i = 0; i < len; i++) {
if (s[i] != ' ') {
if (!wordStarted) {
if (start != 0) s[end++] = ' '; // 添加空格分隔符
start = end; // 记录单词起始位置
wordStarted = true;
}
s[end++] = s[i]; // 复制字符
} else {
wordStarted = false;
}
}
s.resize(end); // 调整字符串长度
reverse(s.begin(), s.end()); // 整体翻转字符串
start = 0;
len = s.size();
for (int i = 0; i < len; i++) {
if (s[i] != ' ' || (i > 0 && s[i - 1] != ' ')) {
s[start++] = s[i]; // 去除多余空格
}
}
s.resize(start);
return s;
}
GPT 给出的时间复杂度可以优化至O(N)的代码（未验证）