0158. Read N Characters Given Read4 II - Call multiple times

题目信息

题号:
  1. 用 Read4 读取 N 个字符 II

难度:

Hard

主题:

字符串、持久缓冲区、外部 API、多次调用状态

原题:

LeetCode 0158

重点:

将 read4 已消费但尚未交付的字符保存在对象成员中,让多次 read 共享一致的逻辑读取位置

题目重述

平台提供 read4(char* buf4),每次从文件当前游标开始最多读取四个字符并推进游标,返回实际读取数。 实现可被调用多次的 read(char* buf, int n):每次按顺序向 buf 写入至多 n 个尚未交付的文件 字符,返回实际写入数。不同 read 调用共享同一文件和同一个 Solution 对象;文件结束时返回不足 n 的数量,之后调用返回零。

自建示例

文件内容为 "abcdefg",在同一对象上依次调用:

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++ 实现

// 平台已提供: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:

调用

补充与复制

返回后的未交付区间

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)。本题的认知增量是跨 调用持久状态,单次调用版不能作为等价第二方案保留。