0158. Read N Characters Given Read4 II - Call multiple times ============================================================ 题目信息 -------- :题号: 0158. 用 Read4 读取 N 个字符 II :难度: Hard :主题: 字符串、持久缓冲区、外部 API、多次调用状态 :原题: `LeetCode 0158 `_ :重点: 将 read4 已消费但尚未交付的字符保存在对象成员中,让多次 read 共享一致的逻辑读取位置 题目重述 -------- 平台提供 ``read4(char* buf4)``,每次从文件当前游标开始最多读取四个字符并推进游标,返回实际读取数。 实现可被调用多次的 ``read(char* buf, int n)``:每次按顺序向 ``buf`` 写入至多 ``n`` 个尚未交付的文件 字符,返回实际写入数。不同 ``read`` 调用共享同一文件和同一个 ``Solution`` 对象;文件结束时返回不足 ``n`` 的数量,之后调用返回零。 自建示例 -------- 文件内容为 ``"abcdefg"``,在同一对象上依次调用: .. code-block:: text read(buf, 1) -> "a",返回 1;内部还保留 "bcd" read(buf, 3) -> "bcd",返回 3;无需再次调用 read4 read(buf, 4) -> "efg",返回 3;文件到达末尾 read(buf, 2) -> "",返回 0 若调用 ``read(buf, 0)``,不应消费现有内部余量,也不应推进文件游标。 C++ 实现 -------- .. code-block:: cpp // 平台已提供:int read4(char* buf4); class Solution { private: char bufferedCharacters_[4]; int nextBufferedIndex_ = 0; int bufferedCount_ = 0; public: int read(char* buf, int n) { int copied = 0; while (copied < n) { if (nextBufferedIndex_ == bufferedCount_) { bufferedCount_ = read4(bufferedCharacters_); nextBufferedIndex_ = 0; if (bufferedCount_ == 0) { break; } } while (copied < n && nextBufferedIndex_ < bufferedCount_) { buf[copied] = bufferedCharacters_[nextBufferedIndex_]; ++copied; ++nextBufferedIndex_; } } return copied; } }; 题解 ---- 与上一题相比,真正变化的是时间边界 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 单次 ``read`` 中,最后一次 ``read4`` 多取的字符在函数返回后再也没人需要,可以丢弃。现在同一个对象会 再次收到 ``read`` 请求,而底层文件游标已经被 ``read4`` 推进;若本次只请求一个字符却读了四个,下次 不能要求 ``read4`` 重读剩余三个,它只会从第五个字符继续。 因此逻辑读取位置与底层文件游标暂时分离:文件游标已经越过整个四字符块,调用者只收到块的一部分。二者 之间的差额必须由 ``Solution`` 对象跨调用保存,局部数组无法承担这种生命周期。 持久状态的精确定义 ~~~~~~~~~~~~~~~~~~ 三个成员共同表示一段已从文件读取、但可能尚未全部交付的数据: * ``bufferedCharacters_``:最近一次 ``read4`` 取得的最多四个字符; * ``bufferedCount_``:该块中实际有效字符数; * ``nextBufferedIndex_``:下一次应交付的块内下标。 任意调用边界上的不变量是:区间 ``bufferedCharacters_[nextBufferedIndex_ .. bufferedCount_-1]`` 恰好包含已被底层文件游标消费、但尚未返回 给调用者的字符,且顺序不变。当两个下标相等时缓存已空,才允许再次调用 ``read4``。 为什么必须先消费旧缓存 ~~~~~~~~~~~~~~~~~~~~~~ 若缓存还有 ``bcd`` 却先调用 ``read4``,新块会覆盖数组并从文件更后方读取,``bcd`` 永久丢失。主循环 只有在 ``nextBufferedIndex_ == bufferedCount_`` 时补充;否则直接进入复制循环,把最早未交付字符写入 本次 ``buf``。 补充缓存时同时把 ``nextBufferedIndex_`` 重置为零,因为新块尚未消费。``read4`` 返回零表示底层文件已 空;此时旧缓存也必已消费完(否则不会进入补充分支),所以可以结束本次调用。 一次调用何时停止 ~~~~~~~~~~~~~~~~ 内层循环同时受两个边界控制:``copied < n`` 防止超过调用者目标, ``nextBufferedIndex_ < bufferedCount_`` 防止读取块内无效位置。可能有两种结果: * 本次目标先写满:保留尚未复制的缓存下标,直接返回,下一次从那里继续; * 缓存先耗尽:返回外层循环,若本次还缺字符就调用 ``read4`` 补充。 因此一次 ``read`` 可能只消费旧缓存,也可能跨越多个四字符块,还可能在新块中间停止;同一套状态覆盖全部 情况。 跨调用具体走读 ~~~~~~~~~~~~~~ 对文件 ``abcdefg``: .. list-table:: :header-rows: 1 * - 调用 - 补充与复制 - 返回后的未交付区间 * - ``read(1)`` - ``read4`` 得到 ``abcd``,复制 ``a`` - 下标 ``1..3``,即 ``bcd`` * - ``read(3)`` - 直接复制旧缓存 ``bcd`` - 空,两个下标都为 ``4`` * - ``read(4)`` - 补充 ``efg``,复制三字;缓存耗尽后下一次 ``read4`` 返回零 - 空,返回数量 ``3`` * - ``read(2)`` - 缓存空且 ``read4`` 返回零 - 空,返回数量 ``0`` 若第二次只请求两个字符,它会返回 ``bc`` 并把下标停在 ``3``,下一次首先返回 ``d``,再决定是否补充。 这个中间状态正是本题不能复用上一题局部临时块的原因。 为什么不需要把余量搬到数组开头 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 可以在每次返回前把剩余字符左移,但块最多四个,且两个下标已经能常数时间描述有效区间。保留原位置只递增 ``nextBufferedIndex_``,直到耗尽后由下一次 ``read4`` 整块覆盖,删除了额外搬移和对应边界分支。 ``n=0`` 与输出终止符 ~~~~~~~~~~~~~~~~~~~ ``n=0`` 时外层条件一开始为假,成员下标和底层文件游标都不变,符合“本次不读取”的语义。和上一题一样, 返回值界定 ``buf[0..copied-1]`` 的有效范围,代码不追加 ``'\0'``;调用者缓冲区未必为终止符多留一个位置。 正确性与复杂度 ~~~~~~~~~~~~~~ 归纳每次复制:算法总从持久未交付区间首字符开始,缓存为空才从底层取得紧随其后的新块,所以跨任意调用 序列,返回字符连接起来恰好是文件前缀且无重无漏。每次调用只在写满 ``n`` 或缓存与文件都无字符时停止, 返回数正确。 一次调用实际返回 ``k`` 个字符时,至多执行 ``O(k/4 + 1)`` 次 ``read4``,总时间 ``O(k + 1)``;跨全部 调用,每个文件字符最多进入缓存一次、交付一次。成员缓冲固定四字符,额外空间 ``O(1)``。本题的认知增量是跨 调用持久状态,单次调用版不能作为等价第二方案保留。