LeetCode 158. 用 Read4 读取 N 个字符 II - 多次调用

2026-05-24 HGNULB 约 5 分钟

文章信息 2 个分类 3 个标签

分类

LeetCode 困难

题目描述

✅ 158. 用 Read4 读取 N 个字符 II - 多次调用

题意分析

系统只提供 read4(buf4)：每次最多从文件读取 4 个字符并返回实际读到的数量。现在要实现 read(buf, n)，把最多 n 个字符写入调用方的 buf，返回本次实际写入的数量；文件提前结束时可以少于 n。

难点不在“凑够 n 个字符”，而在 read 会被多次调用。read4 可能多读：源文件为 "abcdef"，第一次只要求读取 1 个字符，但 read4 已经取出了 abcd。本次只能返回 a，剩余的 bcd 必须保留给下一次调用，绝不能丢弃，也不能再次从文件中读取。

因此缓存不能是 read 的局部变量，而要属于整个 Solution 对象（Go 中属于闭包）。需要永久维护两个下标：缓存中共有多少个有效字符，以及下一个未消费字符的位置。

n = 0 时直接返回 0；当缓存已空且 read4 返回 0 时才真正到达 EOF。缓存中若还有字符，即使底层文件已经读完，也必须先把缓存消费完。

解法：四字符缓存跨调用复用

核心思路

维护固定长度为 4 的缓存 cache，以及两个跨调用字段：

cacheSize：最近一次 read4 写入缓存的有效字符数，范围为 0 到 4；

cacheIndex：缓存中下一个尚未交给调用方的字符下标。

核心不变量是：cache[cacheIndex, cacheSize) 恰好保存已经从底层文件读出、但还没有返回给任何一次 read 调用的字符。

只有在 cacheIndex == cacheSize、也就是缓存完全消费后，才允许再次调用 read4。拿到新数据后把 cacheIndex 重置为 0；如果新 cacheSize 为 0，说明缓存和文件都没有可读字符，结束本次调用。

从缓存向用户缓冲区复制时，同时受两个边界限制：不能超过本次要求的 n，也不能越过缓存有效区。若用户缓冲区先满，缓存剩余部分自然留到下一次调用。

解题步骤

用 written 记录本次已经写入调用方缓冲区的字符数。

当 written < n 时，先检查内部缓存是否为空。

缓存为空则调用一次 read4(cache) 补充，并把 cacheIndex 归零；返回 0 就退出。

在 written < n && cacheIndex < cacheSize 时逐个复制，同时推进两个下标。

返回 written，它表示本次真正交付的字符数，而不是某次 read4 的返回值。

用源文件 "abcdef" 连续调用三次：

read(buf, 1)：read4 取得 abcd，返回 a，内部仍保存 bcd，返回值为 1。

read(buf, 3)：不调用 read4，直接返回缓存中的 bcd，返回值为 3。

read(buf, 4)：缓存为空后调用 read4 得到 ef，复制 2 个字符；下一次 read4 返回 0，于是本次返回 ef，返回值为 2。

三次调用拼接出的内容仍严格是 abcdef，没有重复也没有丢失。

代码实现

class Solution extends Reader4 {
    private final char[] cache = new char[4];
    private int cacheIndex;
    private int cacheSize;

    public int read(char[] buf, int n) {
        int written = 0;
        while (written < n) {
            if (cacheIndex == cacheSize) {
                cacheSize = read4(cache);
                cacheIndex = 0;
                if (cacheSize == 0) {
                    break;
                }
            }

            while (written < n && cacheIndex < cacheSize) {
                buf[written++] = cache[cacheIndex++];
            }
        }
        return written;
    }
}

var solution = func(read4 func([]byte) int) func([]byte, int) int {
    cache := make([]byte, 4)
    cacheIndex, cacheSize := 0, 0

    return func(buf []byte, n int) int {
        written := 0
        for written < n {
            if cacheIndex == cacheSize {
                cacheSize = read4(cache)
                cacheIndex = 0
                if cacheSize == 0 {
                    break
                }
            }

            for written < n && cacheIndex < cacheSize {
                buf[written] = cache[cacheIndex]
                cacheIndex++
                written++
            }
        }
        return written
    }
}

复杂度分析

时间复杂度：单次调用为 $O(k + 1)$，其中 $k \le n$ 是本次实际返回的字符数；至多还会做一次发现 EOF 的常数操作，因此通常写作 $O(n)$。在一系列调用中，每个文件字符只会从内部缓存复制给调用方一次。

空间复杂度：$O(1)$，内部缓存固定为 4 个字符；调用方传入的输出数组不计入额外空间。

关键点总结

158 相比 157 多出来的唯一难点，就是跨调用保存多读的字符。

cacheIndex == cacheSize 是唯一允许补充缓存的时机；只要两者不等，就不能碰底层文件指针。

EOF 的判定条件是“缓存已空且 read4 返回 0”，不能只看某次读取少于 4。

本次返回值是 written，而 cacheSize 只描述内部最近一次批量读取。

面试追问若改成并发调用，应说明当前对象含可变共享状态，并非线程安全；需要外部串行化或为每个独立文件流维护独立读取器。

易错点总结

把缓存和下标定义在 read 内部：源文件 "abcdef" 第一次读 1 个字符后，bcd 随函数返回一起丢失，第二次会直接从 e 开始。

每轮循环都调用 read4：缓存尚有 bcd 时又读取 ef，会覆盖未消费数据并破坏文件顺序。

用户缓冲区满后丢弃缓存尾部：第一次 read(buf, 1) 不能把 bcd 当成“本次不需要”而清空，它们属于后续调用。

用 cacheSize < 4 直接停止复制：最后一次 read4 返回 2 仍代表两个有效字符，必须先交付 ef；少于 4 只说明可能已到文件尾附近。

返回 cacheSize：一次调用可能先消费旧缓存、再读新缓存，某次 read4 的数量不等于本次总写入量。

n = 0 时仍调用 read4：这会无故推进底层文件指针，使下一次真正读取时丢失开头字符。

相似题目

题目	难度	考察点
157. 用 Read4 读取 N 个字符	简单	只调用一次，不需要保存跨调用缓存，可用于对比本题新增状态
251. 展开二维向量	中等	迭代器需要跨多次 `next` 调用保存当前位置
281. 锯齿迭代器	中等	多数据源轮转读取，重点也是持久化消费进度
284. 窥视迭代器	中等	预读一个元素并缓存，和 `read4` 多读后的处理方式相似