面试题5：替换空格

从We are happy.开始

先预测：把空格替换成%20时，若从左向右写，第一次把%写进空格位置后，原来位于右侧的字符应该放到哪里？若缓冲区中直接展开，每遇到一个空格都要把后缀整体右移两格；多个靠前空格会反复搬动同一批字符。

这道“替换空格”要求把字符数组中的每个空格替换为"%20"。作者接口接收可写char[]和缓冲区总长度，数组预留了扩展空间。核心不是调用现成字符串替换，而是证明在同一缓冲区中如何不覆盖尚未读取的字符。

原字符串可见长度为originalLength，空格数为spaces。每个空格原占1个字符，替换后占3个字符，所以净增2；新可见长度为originalLength + 2 * spaces。C字符串还必须保存结尾\0，实际需要的槽位比新可见长度多1。

是算法成立的前提。容量不足时必须在开始后向写之前返回失败，避免写出边界或只改一半。

为什么前向移动会重复工作

假设字符串长度为n，前面有多个空格。左到右遇到第一个空格时，要把几乎整个后缀右移两位；遇到第二个空格，又移动大部分后缀。最坏情况下，总搬移量形成n + (n-1) + ...量级，时间退化到O(n²)。

若另建输出数组，左到右追加当然可以O(n)，但额外空间是O(n)。原题刻意给出扩展后的原缓冲区，要求利用已有空间实现常数额外状态。

后向方案先扫描得到最终边界，让直接把每个字符放到最终位置。写入发生在尚未读取区域的右侧，已写内容和待读内容不会冲突。

两个指针各守一条边界

从原可见长度开始，因此第一次读取的是\0；从新可见长度开始。先复制终止符，保证最终字符串仍正确结束。

普通字符只需写一次，两个指针各左移1。遇到空格时，从右向左依次写'0'、'2'、'%'；内存正序读出就是%20。读指针左移1，写指针左移3。

循环只在write > read时需要实际复制。当两个指针相遇，说明剩余前缀没有扩展差额，原字符已经处在最终位置。写成read >= 0也能工作，但会做额外的原位复制；使用有符号下标时两种条件都容易表达。

不能漏掉。若只从originalLength-1开始复制可见字符，却没有在newLength写\0，后续strlen和输出函数会继续读取旧内存，产生乱码或越界。

容量安全的C++实现

官方代码先统计实际长度和空格数，再比较新长度与传入容量，最后从两个末尾下标回写。下面用std::span<char>让容量与指针一起传入，并补齐缺失终止符与算术溢出检查：

#include <cstddef>
#include <limits>
#include <span>
 
bool replace_spaces(std::span<char> buffer) {
    if (buffer.empty()) {
        return false;
    }
 
    std::size_t original_length = 0;
    std::size_t spaces = 0;
    while (original_length < buffer.size() &&
           buffer[original_length] != '\0') {
        if (buffer[original_length] == ' ') {
            ++spaces;
        }
        ++original_length;
    }
 
    if (original_length == buffer.size()) {
        return false; // 容量内没有终止符
    }
    if (spaces > (std::numeric_limits<std::size_t>::max()
                  - original_length) / 2) {
        return false;
    }
 
    const std::size_t new_length = original_length + spaces * 2;
    if (new_length >= buffer.size()) {
        return false; // 还需要buffer[new_length]存放'\0'
    }
 
    std::ptrdiff_t read =
        static_cast<std::ptrdiff_t>(original_length);
    std::ptrdiff_t write =
        static_cast<std::ptrdiff_t>(new_length);
 
    while (read >= 0 && write > read) {
        if (buffer[read] == ' ') {
            buffer[write--] = '0';
            buffer[write--] = '2';
            buffer[write--] = '%';
        } else {
            buffer[write--] = buffer[read];
        }
        --read;
    }
    return true;
}

这里new_length >= buffer.size()才是容量不足，因为buffer[new_length]要保存终止符。若把条件写成只在new_length > capacity时失败，当二者相等就会写到最后一个合法下标之后。

作者源码的空输入判断形如str == nullptr && length <= 0。健壮接口应分别拒绝空指针或非正容量，逻辑是“或”；否则空指针配正长度仍会进入扫描。std::span把空指针与长度组合封装起来，但空span仍需判断。

不可变字符串语言的实现边界

JavaScript与TypeScript字符串不可原地修改。可以使用结果字符数组后向填充，算法仍展示相同读写关系，但额外空间是O(n)，不能声称原地O(1)：

function replaceSpaces(text: string): string {
  let spaces = 0;
  for (const char of text) {
    if (char === " ") spaces += 1;
  }
 
  const output = new Array<string>(text.length + spaces * 2);
  let read = text.length - 1;
  let write = output.length - 1;
 
  while (read >= 0) {
    if (text[read] === " ") {
      output[write--] = "0";
      output[write--] = "2";
      output[write--] = "%";
    } else {
      output[write--] = text[read];
    }
    read -= 1;
  }
  return output.join("");
}

若只需要得到新字符串，正向构建通常更自然；这里保留后向版本用于对应原题缓冲区推理。语言的字符串模型改变空间结论，不能把C++的“原地”标签原样复制到不可变字符串。

%20在本题中是固定替换标记，不等于完整URL编码器。真实URL应区分路径、查询、表单编码和字符集，使用平台标准库；某些表单编码会把空格写成+，保留字符的规则也不同。面试题训练缓冲区扩展，不应被包装成通用网络安全方案。

正确性与复杂度

后向循环保持不变式：write右侧已经是最终输出后缀，read左侧和尚未读取的原前缀仍保持完整，且待写边界不在待读边界左侧。普通字符消耗1个源槽和1个目标槽，空格消耗1个源槽并生成3个目标槽，正好解释两指针距离变化。

第一次扫描读取每个字符一次；第二次后向复制再次读取每个原字符，并写出每个结果字符。工作量与输入和输出长度之和成正比，在每个空格最多展开固定3字符时可记为O(n)。额外只保存长度、计数和两个下标，为O(1)。

若替换串长度不是固定3，而由输入决定，复杂度应写成O(n + outputLength)。若缓冲区容量由不可信整数传入，还要检查乘法和加法溢出；否则一个很小的回绕newLength会绕过容量检查。

测试覆盖位置、密度和容量

失败原子性、字节语义与接口设计

两遍算法还有一个容易忽略的收益：第一遍能在任何写入发生前算出所需容量。若容量不足、输入未终止或长度算术溢出，函数可以返回失败并保持原缓冲区不变。调用者随后分配更大空间重试，不必猜测哪些字符已经被改写。

更实用的接口可返回所需槽位数，而不是只有布尔值。例如先调用查询模式得到required = newLength + 1，再提供足够缓冲区执行；这与许多C API的长度协商方式一致。若仍使用布尔结果，错误枚举至少应区分空输入、缺失终止符和容量不足，方便日志与恢复。

后向复制与memmove处理重叠区域的方向选择相似：目标区域起点位于源区域右侧时，从尾部复制可以防止覆盖未读源字节。但这里不只是移动同一段字节，空格还要展开成三个新字节，所以不能用一次memmove完成全部替换；可以把连续普通片段批量移动，但会增加实现复杂度，只有测量证明有收益才值得。

原题的char算法按字节识别ASCII空格0x20，并写ASCII字符%20。UTF-8中普通非ASCII字符由多个字节组成，逐字节原样后向复制仍能保持其字节序，因为每个字节的相对顺序不变；但它不会识别全角空格、不换行空格等其他Unicode空白。需求若说“所有空白字符”，就必须按Unicode码点或分词规则解析，不能继续用char == ' '。

同理，缓冲区可能含嵌入的零字节。C字符串语义把第一个\0当结束，后续字节不属于文本，算法不会处理它们。若数据是长度明确的二进制片段，接口应接收实际长度而非扫描终止符，并重新定义哪些字节需要替换。

两个指针的安全关系还依赖最终长度不小于原长度。当前替换把1字节扩为3字节，写指针初始不会在读指针左侧；若改成“把多个字符压缩成一个”，应从前向后写，后向方案反而可能覆盖待读内容。方向由源目标区域的相对位置决定，不是双指针题一律从后开始。

线程安全方面，函数独占可写缓冲区是隐含前提。另一个线程若同时读取，可能看见终止符已移动而中间尚未全部填充的瞬态；另一个写线程则会直接造成数据竞争。需要外部同步或先在私有缓冲区构造，再原子发布结果。

作者九组测试依次覆盖：空格在中间、开头、结尾；连续两个空格；空指针；空字符串；单个空格；没有空格；全部是空格。工程补充还应验证容量恰好足够、少一个槽、容量内无\0和算术边界。

#include <array>
#include <cassert>
#include <cstring>
 
void test_replace_spaces() {
    std::array<char, 32> middle{};
    std::strcpy(middle.data(), "hello world");
    assert(replace_spaces(middle));
    assert(std::strcmp(middle.data(), "hello%20world") == 0);
 
    std::array<char, 16> adjacent{};
    std::strcpy(adjacent.data(), "a  b");
    assert(replace_spaces(adjacent));
    assert(std::strcmp(adjacent.data(), "a%20%20b") == 0);
 
    std::array<char, 4> too_small{};
    std::strcpy(too_small.data(), "a ");
    const auto before = too_small;
    assert(!replace_spaces(too_small));
    assert(too_small == before);
}

容量不足测试还确认函数在开始回写前失败，输入保持原样。这比只断言返回false更强：调用者可以在失败后安全重试更大缓冲区。

本章练习

概念说明

本章核心概念包括：从后向前复制。理解这些概念是掌握解题方法的关键，需要结合具体示例与边界条件反复练习。

本章回顾

1. 前向原地展开会反复移动后缀，最坏可能O(n²)。
2. 每个空格替换为%20后净增2，新可见长度是原长度加两倍空格数。
3. 缓冲区还需一个\0槽，newLength等于容量仍是不够。
4. 两个指针从后向前复制，普通字符写1格，空格逆序写3格。
5. 后向复制保持未读前缀不被覆盖，时间O(n)、额外空间O(1)。
6. C字符串必须在容量内找到终止符；空指针、容量和算术溢出都要在写入前检查。
7. 不可变字符串语言需要新结果存储，算法思路相同但空间不是O(1)。
8. 本题的固定%20替换不等于完整URL编码。

名词解释