LeetCode 158. 用 Read4 读取 N 个字符 II - 多次调用
题目描述
题意分析
read4(buf4)每次最多从文件读取 4 个字符，返回实际读取数量。需要实现的read(buf, n)则把最多n个字符放入调用方的buf，并返回本次真正写入的数量；文件剩余内容不足时允许少于n。同一个读取器会被多次调用，而底层文件位置只会向前移动。比如文件为
"abcdef"，第一次只要 1 个字符，read4却可能已经取出abcd。交付a后必须保存bcd，否则下一次会直接从e开始，丢失已经读出的内容。因此要分清“从文件读出”和“交给调用方”两个进度。内部缓存保存两者之间的差额，必须跨调用存在；每次调用单独从
buf[0]开始写入，并重新统计返回数量。
解法：四字符缓存跨调用复用
核心思路
[!blue]
用固定长度为 4 的
cache保存最近一次批量读取，再维护两个持久状态：cacheSize是有效字符数，cacheIndex是下一个尚未交付的字符下标。始终满足0 <= cacheIndex <= cacheSize <= 4。区间
cache[cacheIndex, cacheSize)就是已经从文件取出、还没有交给调用方的内容。只要这个区间非空，就必须先消费它；只有cacheIndex == cacheSize时才能调用read4覆盖缓存，并把下标重置为 0。每次复制同时推进本次计数
written与缓存下标cacheIndex，但停止条件有两个：written == n表示本次需求已经满足；cacheIndex == cacheSize表示缓存暂时耗尽，需要补充。前者可以保留未消费缓存，后者不代表本次一定结束。本次尚未读够时，若缓存耗尽且新一次
read4返回 0，当前实现就因没有更多内容而结束读取。若某次read4返回 1 到 3，虽然已经读到了文件尾，返回的这些字符仍必须先交付或留待后续调用，不能丢弃。无需额外保存 EOF 标记，再次返回 0 也能正确结束。
解题步骤
- 对象字段或 Go 闭包保存
cache、cacheIndex、cacheSize；每次read只把written初始化为 0。- 在
written < n时继续处理。缓存为空就调用read4补充，若实际读入数量为 0，立即退出。- 在本次尚未读够、缓存也尚未用完时，逐个复制字符到
buf[written]，同时推进两个位置。- 返回
written，其余缓存状态原样保留给下次调用。对文件
"abcdef"连续请求 1、3、4 个字符：第一次读取abcd但只交付a；第二次直接交付缓存中的bcd；第三次补充ef，交付后再次补充得到 0，因此返回 2。每个字符只交付一次，顺序也不变。
代码实现
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$ 为实际返回的字符数，且 $k <= n$。除逐字复制外，每次补充最多读 4 个字符，末尾至多再做一次读到 0 的操作。
- 空间复杂度：$O(1)$，缓存固定为 4 个字符，两个持久下标与本次计数均占常数空间，不计调用方的输出数组。
关键点总结
[!green]
- 持久状态描述内部缓存，本次局部状态
written描述当前输出，不能互相替代。- 缓存未空时不读文件，保证未消费字符不会被覆盖，也保证交付顺序正确。
n = 0时循环不进入，返回 0 且不改变缓存或底层文件位置。- 读到文件尾与交付完缓存是两件事：底层没有新字符时，缓存仍可能留有可返回内容。
易错点总结
[!yellow]
- 把缓存放在
read内部：调用结束会丢掉本次多读的字符，无法支持连续读取。- 每轮无条件调用
read4：旧缓存中的剩余字符会被覆盖，必须先判断是否已消费完。- 把读取不足 4 当成零字符：返回 2 就仍有两个有效字符，要先复制，再决定是否继续。
- 复制时只检查一个边界：只检查
n会读过缓存有效区，只检查缓存会写过本次请求数量。- 返回
cacheSize：一次调用可能跨多个缓存批次，也可能只消费部分缓存，只有written表示本次返回数量。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 157. 用 Read4 读取 N 个字符 | 简单 | 原题只调用一次read，多读尾部无需留给后续调用，本题必须跨调用保留缓存。 |
| 251. 展开二维向量 | 中等 | 同样封装持续迭代状态，本题还要处理底层批量读取与上层少量消费的差异。 |