教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载导读LeetCode 0157「用 Read4 读取 N 个字符」是一道经典的交互式模拟题题目禁止直接操作文件只允许通过给定的read4底层 API 按 4 字符一批的方式读取要求在此基础上实现一个能读取恰好 $n$ 个字符的read方法。本文以 AlgoNote「算法通关手册」中的题解文档为主体系统拆解read4的调用契约、模拟循环的算法设计与缓冲区拷贝细节并延伸讲解其进阶版 0158「多次调用」的缓存处理方案。读完本文你将掌握「在受限 API 之上封装高层读取接口」这类交互式模拟题的通用套路以及文件指针推进、剩余字符数控制、提前结束等边界处理技巧。题目概况该题在 AlgoNote「算法通关手册」中位于0100-0199 题解目录在完整题解列表中登记的信息如下项目内容题号0157题名用 Read4 读取 N 个字符标签数组、交互、模拟难度简单从标签可以看出本题既考察对数组缓冲区的基本操作又属于交互类题目依赖给定的 API 完成功能核心是模拟read4的读取过程。题目要求在受限 API 之上实现读取read4 API 契约给定文件只能通过read4方法读取其行为如下read4从文件中读取4 个连续的字符并将它们写入缓存数组buf4返回值是实际读取的字符个数read4()自身维护文件指针类似 C 语言中的FILE *fp每次调用后指针自动前进。其接口定义伪代码形式为参数类型: char[] buf4 返回类型: int关键注意点buf4[]是目标缓存区而非源缓存区read4读取的结果会复制到buf4[]中。开发者不能假设buf4里已有数据也不能指望read4在调用间隙保留上次结果。read4 的行为示例原文档给出了一个直观的例子说明文件指针fp如何随调用推进File file(abcde); // 文件名为 abcde初始文件指针 (fp) 指向 a char[] buf4 new char[4]; // 创建一个缓存区使其能容纳足够的字符 read4(buf4); // read4 返回 4。现在 buf4 abcdfp 指向 e read4(buf4); // read4 返回 1。现在 buf4 efp 指向文件末尾 read4(buf4); // read4 返回 0。现在 buf4 fp 指向文件末尾可以总结出read4的三个关键行为模式满批返回文件剩余字符不少于 4 个时一次返回 4 个字符fp 前进 4 位余量返回文件剩余字符不足 4 个时返回剩余的实际个数13fp 到达文件末尾空返回文件已读完时返回 0buf4内容无效这是终止循环的信号。read 方法要求需要实现的read方法定义如下参数类型: char[] buf, int n 返回类型: int要求是通过反复调用read4完成以下目标从文件中读取 $n$ 个字符并存储到目标缓存数组buf中不能直接操作文件文件只能通过read4获取不能通过read直接读取返回实际读取的字符数。原文档还给出了三条重要约束每个测试用例中read函数只调用一次这是与 0158 多次调用版本的核心区别目标缓存数组buf保证有足够的空间存下 $n$ 个字符无需考虑扩容buf[]是目标缓存区需要将结果写入其中返回值是实际写入的字符总数。示例解析原文档提供了四个测试用例覆盖了「文件比 n 短」「文件恰好等于 n」「文件远长于 n」三种典型情况示例 1file abc, n 4输出3。输入file abc, n 4 输出3 解释当执行你的 read 方法后buf 需要包含 abc。文件一共 3 个字符因此返回 3。此时文件在第一次read4后即被读完返回 3而非 4虽然 n 4但实际只能返回 3 个字符。示例 2file abcde, n 5输出5。输入file abcde, n 5 输出5 解释当执行你的 read 方法后buf 需要包含 abcde。文件共 5 个字符因此返回 5。第一次read4读满 4 个字符第二次再读 1 个字符即满足 n但第二次read4实际上会把文件中剩余的 1 个字符e也读入buf4因此返回值是 5。示例 3file abcdABCD1234, n 12输出12。输入file abcdABCD1234, n 12 输出12 解释当执行你的 read 方法后buf 需要包含 abcdABCD1234。文件一共 12 个字符因此返回 12。文件恰好 12 个字符三次read4各读 4 个字符全部满足。示例 4file leetcode, n 5输出5。输入file leetcode, n 5 输出5 解释当执行你的 read 方法后buf 需要包含 leetc。文件中一共 5 个字符因此返回 5。这是最考验边界处理的用例文件有 8 个字符第一次read4读入 leet第二次read4读入 code但只需要前 1 个字符 c。剩余的 ode 三个字符在本版本单次调用中被丢弃是允许的buf最终只需包含 leetc。解题思路模拟 循环调用 read4算法设计这道题的核心是用read4组装出read属于典型的「API 封装」型模拟。原文档给出的算法步骤为创建一个临时缓冲区buf4用于存储每次read4读取的 4 个字符循环调用read4每次最多读取 4 个字符将读取的字符复制到目标缓冲区buf中但不能超过 $n$ 个字符如果read4返回的字符数少于 4说明文件已读完提前结束返回实际读取的字符总数。关键点剖析从原文档的解题思路中可以提炼出三个必须处理好的细节每次调用read4最多读取 4 个字符但实际可能少于 4 个文件末尾场景因此不能假设每次都能读满需要控制总共读取的字符数不超过 $n$当read4返回 4 个字符但剩余需求不足 4 个时只拷贝需要的部分多余的丢弃本版本允许使用变量total记录已读取的字符总数既是buf的写入游标也是最终的返回值。一个容易被忽略的终止条件while total n循环内部若read4返回count 0表示已经读到文件末尾必须立即break否则会因为count 0导致copy_count 0而陷入死循环。这正是示例 1 中file abc, n 4场景下提前退出的关键。完整实现代码以下是原文档提供的 Python 参考实现含注释 The read4 API is already defined for you. param buf4, a list of characters return an integer def read4(buf4): # Below is an example of how the read4 API can be called. file File(abcdefghijk) # File is abcdefghijk, initially file pointer (fp) points to a buf4 [ ] * 4 # Create buffer with enough space to store characters read4(buf4) # read4 returns 4. Now buf [a,b,c,d], fp points to e read4(buf4) # read4 returns 4. Now buf [e,f,g,h], fp points to i read4(buf4) # read4 returns 3. Now buf [i,j,k,...], fp points to end of file class Solution: def read(self, buf, n): :type buf: Destination buffer (List[str]) :type n: Number of characters to read (int) :rtype: The number of actual characters read (int) total 0 # 已读取的字符总数 buf4 [] * 4 # 临时缓冲区 while total n: # 调用 read4 读取最多 4 个字符 count read4(buf4) # 如果读到文件末尾提前结束 if count 0: break # 计算本次应该复制的字符数不能超过剩余需要读取的字符数 copy_count min(count, n - total) # 将字符复制到目标缓冲区 for i in range(copy_count): buf[total] buf4[i] total 1 return total代码逐行解读临时缓冲区的初始化buf4 [] * 4每次调用read时创建或复用因为本题read每个测试用例只调用一次无需在实例层面保存状态循环条件while total n只有尚未读够 $n$ 个字符时才继续避免无意义的read4调用文件末尾检测if count 0: break是循环退出的另一条路径处理「文件比 n 短」的情况拷贝数量控制copy_count min(count, n - total)同时处理两种约束——read4实际返回的字符数、以及剩余还需要读取的字符数。以示例 4 为例第二次read4返回 4但n - total 1copy_count 1只拷贝buf4[0]字符 c到buf[4]逐个拷贝for i in range(copy_count)将buf4前copy_count个字符按序写入buf并从total位置开始保证字符顺序与文件中一致。复杂度分析原文档给出的复杂度结论为时间复杂度$O(n)$其中 $n$ 是需要读取的字符数。最多需要调用 $\lceil n / 4 \rceil$ 次read4每次调用固定处理不超过 4 个字符总工作量与 $n$ 线性相关空间复杂度$O(1)$只使用了固定大小的临时缓冲区buf4大小为 4不随输入规模增长。边界情况与易错点总结综合四个测试用例可以把本题的边界情况归纳如下场景触发条件处理方式文件比 n 短示例 1abc / n4read4返回 0 时break返回实际读到的字符数文件恰好等于 n示例 2、示例 3循环正常结束total n文件长于 n但 n 不是 4 的倍数示例 4leetcode / n5copy_count min(count, n - total)截断多余字符文件长于 n且 n 是 4 的倍数n8文件更长最后一次read4返回 4拷贝后total n循环条件退出多读的字符被丢弃易错点忘记count 0的提前终止判断导致死循环用count而不是min(count, n - total)作为拷贝数量导致buf中写入超过 $n$ 个字符忽略buf4是目标缓存区这一性质误把buf4当源数据直接使用在拷贝时写错下标例如从buf4[0]而非buf4[total]拷贝或写入buf[total]之外的错误位置。进阶延伸0158 多次调用版本理解本题后值得关注 AlgoNote 手册中紧邻的进阶题0158「用 Read4 读取 N 个字符 II - 多次调用」标签同为数组、交互、模拟难度为困难。与 0157 的唯一区别是read方法会被多次调用。原 0157 的解法中示例 4 场景下多读出的 ode 三个字符被直接丢弃而 0158 要求这些字符在后续调用中继续可用因此不能丢弃必须保存。其核心方案是使用实例变量self.buffer保存上次调用read4时多读取的字符使用实例变量self.buffer_ptr和self.buffer_count记录缓冲区的读取位置和有效字符数每次调用read时先消耗内部缓冲区中的剩余字符不够时再调用read4补充直到读满 $n$ 个字符或文件结束。class Solution: def __init__(self): # 内部缓冲区保存上次多读取的字符 self.buffer [] * 4 self.buffer_ptr 0 # 缓冲区读取指针 self.buffer_count 0 # 缓冲区有效字符数 def read(self, buf, n): total 0 # 已读取的字符总数 while total n: # 如果缓冲区为空调用 read4 读取新字符 if self.buffer_ptr self.buffer_count: self.buffer_count read4(self.buffer) self.buffer_ptr 0 # 如果读到文件末尾结束 if self.buffer_count 0: break # 从缓冲区复制字符到目标缓冲区 while total n and self.buffer_ptr self.buffer_count: buf[total] self.buffer[self.buffer_ptr] total 1 self.buffer_ptr 1 return total该进阶版的复杂度同样为 $O(n)$ 时间、$O(1)$ 空间但额外多了一个「消费剩余 → 补充新批」的状态机循环。建议将两道题对照阅读0157 是「一次性读取」的简化版0158 是在其基础上加入内部缓存状态的完整版二者共同构成了「受限 API 封装」类题目的完整解法图谱。总结本题虽标注为「简单」却完整覆盖了交互式模拟题的三个核心考点理解并遵守 API 契约read4的返回值语义、buf4的目标缓存区性质、文件指针的自动推进循环 截断的读取框架while total n、min(count, n - total)、count 0提前退出三者缺一不可缓冲区拷贝的正确性写入游标total与拷贝源下标buf4[i]的对应关系。在 AlgoNote「算法通关手册」中本题解位于0100-0199 题解目录读者还可以在完整题解列表中按标签数组、交互、模拟检索同类题目并对照0158 进阶题解加深对「多次调用 内部缓存」场景的理解。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐AlgoNote 算法通关手册LeetCode 0066「加一」数组模拟加法题解AlgoNote 算法通关手册LeetCode 0066「加一」数组模拟加法题解 本篇技术指南以「算法通关手册」AlgoNote仓库中 LeetCode教程文档知识库AlgoNote 算法通关手册KMP 字符串匹配算法详解与 Python 实战AlgoNote 算法通关手册KMP 字符串匹配算法详解与 Python 实战 本文是「算法通关手册」字符串专题的核心篇章系统讲解 KMPKnuth Mo教程文档知识库AlgoNote 算法通关手册LeetCode 0087 扰乱字符串Scramble String三维动态规划详解AlgoNote 算法通关手册LeetCode 0087 扰乱字符串Scramble String三维动态规划详解 导读 本文是 AlgoNote「算法通教程文档知识库上一篇Llama-2-7B-Chat-GGML量化版本完整清单14个文件2~8位精度如何快速选对下一篇Starship 的 Tokyo Night 预设完全指南用一条命令把提示符变成东京夜色创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考