LeetCode 157. 用 Read4 读取 N 个字符

约 5 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 简单 未解决 1-2 字节跳动
标签
数组 模拟 交互
目录

题目描述

✅ 157. 用 Read4 读取 N 个字符

题意分析

系统只给了一个底层接口 read4(buf4)：它从一个文件里读取字符，一次最多读 4 个，写进调用者提供的 4 字节缓冲区，返回实际读到的个数。要用它实现 read(buf, n)，把最多 n 个字符读进 buf，并返回实际读到的个数。

「最多 n 个」是关键措辞：文件可能比 n 短，此时能读多少算多少，返回值就是真实读到的数量，而不是 n。所以返回值必须是累计计数，不能无脑返回 n。

read4 的返回值本身携带了两条信息：一是这次实际拿到几个字符，二是文件有没有到底。返回值小于 4 就说明文件读完了；返回 0 更是明确的终止信号。这两点决定了循环的退出条件有两个而不是一个。

4 与 n 之间没有整除关系，所以最后一批必然可能读多。比如 n = 5 时第二次 read4 会拿回 4 个字符，但只能用其中 1 个，多出来的 3 个不能写进 buf，否则就越界或污染了调用方的缓冲区。这是本题唯一真正的技术点。

题目还有一个隐含前提：read 只会被调用一次，所以不需要在两次调用之间保存上次没用完的字符（那是 158 题的事）。多读出来的字符直接丢弃即可。

边界上 n = 0 时应当一次 read4 都不调用、直接返回 0；文件为空时第一次 read4 就返回 0，同样返回 0。

解法：分批 read4 拷贝

核心思路

read4 每次最多返回 4 个字符，但目标缓冲区本轮可能只剩不足 4 个位置。因此每轮真正复制的数量是 min(count, n-copied)，其中 count 是本次底层读取量。

维护 copied 表示已经写入目标数组的字符数。循环只在 copied < n 时调用 read4；复制本批可用字符后，若 count < 4，说明已经到达文件末尾，立即停止。

不变量：每轮开始时，buf[0..copied) 恰好是文件开头的 copied 个字符，且 0 <= copied <= n。本轮只追加临时缓冲区的前 take 个字符，因此顺序和边界继续成立。

正确性：每次 read4 返回的字符都按原顺序复制，且不会超过调用方要求的 n 个。循环因读满 n 或文件结束而停止，所以返回值恰好是实际复制数量。题目保证 read 只调用一次，本批多读但未使用的字符无需跨调用保存。

解题步骤

  1. 创建长度为 4 的临时缓冲区，初始化 copied=0。
  2. 当 copied<n 时调用 read4，计算 take=min(count,n-copied)。
  3. 将临时缓冲区前 take 个字符复制到 buf，同步增加 copied。
  4. 若 count<4，文件已结束；否则继续读取下一批。
  5. 返回 copied。

文件为 "abcdefg"、n=5 时，两次 read4 分别返回 4 和 3；第二批只复制 e，最终返回 5。多出的 f、g 在本题单次调用语义下可以丢弃。

边界上，n=0 时不得调用 read4；文件为 "ab"、n=5 时首批返回 2，复制后立即结束并返回 2。

代码实现

public class Solution extends Reader4 {
    public int read(char[] buf, int n) {
        char[] tmp = new char[4];
        int copied = 0;

        while (copied < n) {
            int cnt = read4(tmp);
            int take = Math.min(cnt, n - copied);
            System.arraycopy(tmp, 0, buf, copied, take);
            copied += take;
            if (cnt < 4) {
                break;
            }
        }

        return copied;
    }
}

func read(buf []byte, n int) int {
	tmp := make([]byte, 4)
	copied := 0

	for copied < n {
		cnt := read4(tmp)
		take := cnt
		if n-copied < take {
			take = n - copied
		}
		copy(buf[copied:], tmp[:take])
		copied += take
		if cnt < 4 {
			break
		}
	}

	return copied
}

复杂度分析

  • 时间复杂度：$O(n)$，最多复制 n 个字符，并调用 $O(\lceil n/4 \rceil)$ 次 read4。
  • 空间复杂度：$O(1)$，临时缓冲区固定为 4 个字符。

关键点总结

  • 底层读取量与本轮需求量不同，复制量必须取两者较小值。
  • count<4 表示文件结束，但这一批已有字符仍要先复制。
  • n=0 时循环不进入，避免无意义地推进底层文件指针。
  • 返回实际复制量，不假设文件一定有 n 个字符。
  • 本题只调用一次 read，无需保存本轮多读字符；多次调用版本才需要持久缓冲区。

易错点总结

  • 每批全部复制：文件 "abcdefg"、n=5 时第二批会越过目标缓冲区边界。
  • 在 count<4 时先退出再复制：文件 "abc" 会错误返回 0。
  • take=min(count,n)：第二批没有扣除已复制数量，仍可能越界。
  • 不处理 count=0：它也满足 count<4；若不退出，文件较短时会死循环。
  • 固定返回 n：文件不足时会把未写入位置冒充有效字符。
  • 为单次调用保存剩余字符：不影响正确性，但增加了本题不需要的跨调用状态。

相似题目

题目 难度 考察点
158. 用 Read4 读取 N 个字符 II - 多次调用 困难 必须跨调用缓存上次多读的字符，需要持久化缓冲区与消费指针
341. 扁平化嵌套列表迭代器 中等 同样要把底层不规则的数据源包装成按需取用的接口，靠栈做惰性展开
281. 锯齿迭代器 中等 多个数据源轮流取值，重点在 hasNext 与 next 的状态一致性
251. 展开二维向量 中等 需要跳过空的子数组，指针推进逻辑必须在取值前完成对齐
173. 二叉搜索树迭代器 中等 把递归遍历改写成可暂停的显式栈，考的是控制流的手工拆解
622. 设计循环队列 中等 定长缓冲区上的读写指针管理，与本题的临时缓冲区管理同源
1188. 设计有限阻塞队列 中等 生产消费两端都要处理缓冲区满与空的边界，多了并发同步的维度