0157. Read N Characters Given Read4¶
题目信息¶
- 题号:
用 Read4 读取 N 个字符
- 难度:
Easy
- 主题:
字符串、缓冲区、外部 API、边界控制
- 原题:
- 重点:
用四字符临时块隔离 read4 的读取粒度与目标缓冲区剩余空间,并以复制量作为返回状态
题目重述¶
平台提供 read4(char* buf4):它从文件当前读取位置开始,最多读取四个字符到容量至少为四的 buf4,
返回实际读取数;到达文件末尾时返回值可能小于四,文件已读完时返回零。
实现 read(char* buf, int n),把文件开头至多 n 个字符写入调用者缓冲区 buf,返回实际写入数。
实际文件可能短于 n。本题只调用一次 read,不要求为下一次调用保留本次 read4 多取的字符。
自建示例¶
文件内容为
"leetcode"、n = 5:写入"leetc"并返回5;第二次read4虽读到"code",本次只复制其中一个字符;文件内容为
"abc"、n = 5:第一次read4返回3,写入三个字符并返回3;n = 0:不应调用read4,直接返回0。
C++ 实现¶
// 平台已提供:int read4(char* buf4);
#include <algorithm>
class Solution {
public:
int read(char* buf, int n) {
int copied = 0;
char block[4];
while (copied < n) {
const int available = read4(block);
if (available == 0) {
break;
}
const int toCopy = std::min(available, n - copied);
for (int index = 0; index < toCopy; ++index) {
buf[copied] = block[index];
++copied;
}
if (available < 4) {
break;
}
}
return copied;
}
};
题解¶
两个缓冲区的容量规则并不相同¶
read4 只知道自己的固定粒度:一次可能写入零到四个字符。调用者的 buf 则只保证要接收本题要求的
至多 n 个字符;当还差一两个字符时,直接执行 read4(buf + copied) 仍可能写四个字符,越过目标
缓冲区边界。即使没有越界,函数也不能把多写字符计入返回结果。
因此需要容量固定为四的临时数组 block。read4 只写临时块,算法再根据目标剩余空间决定复制前几项,
把外部 API 的读取粒度与输出缓冲区的写入上限隔离。
循环状态分别表示什么¶
copied 始终表示已经写入 buf[0..copied-1] 的字符数,也是下一写入位置。每轮有两个不同数量:
available:这次从文件实际取到block的字符数,范围0..4;toCopy:本次允许写入目标的字符数,即min(available, n-copied)。
二者不能混用。文件可能提供四个字符,但目标只剩一个空位,此时 available=4、toCopy=1;返回状态
只能增加一。
文件与目标状态 |
|
|
|
|---|---|---|---|
|
|
|
|
文件继续为 |
|
|
|
文件 |
|
|
|
两个停止条件对应两种完成原因¶
外层条件 copied < n 表示调用者仍需要字符;一旦写满目标,不能再调用 read4。若
available == 0,文件在本轮开始时已经没有字符,立即停止。若 available < 4,本次已经取得文件
剩余全部字符;复制后即使仍未达到 n,下一次调用也只会返回零,所以可以直接结束。
available < 4 的判断要放在复制之后,否则文件最后一块会被漏掉。available == 0 提前分支虽然也
满足小于四,但避免进入零次复制,并更直接表达文件已空。
为什么多读字符在本题可以丢弃¶
leetcode、n=5 的第二次 read4 会推进文件位置四个字符,而这里只复制 c,临时块中的
ode 没有写入输出。本题保证 read 只调用一次,这些余量不会被未来请求需要,因此丢弃不影响本次
返回值。
若接口允许连续多次调用 read,这三个字符必须跨调用保存,否则下一次会从文件更后方开始并漏数据;那
需要成员缓冲区、已消费下标和剩余数量,是下一题的新增状态。不能把单次调用的正确实现直接宣称适用于多次
调用。
输出不是 C 风格终止字符串¶
函数契约以返回的 copied 指明有效字符范围,没有要求在 buf[copied] 写 '\0'。擅自追加终止符
可能越过恰好为 n 的缓冲区,也会把文件内容与字符串表示规则混在一起。代码只写实际读取字符。
正确性与复杂度¶
每次循环从文件顺序取得下一块,并按块内顺序复制不超过目标剩余容量的前缀,所以 buf 始终等于文件
开头尚未超过 n 的已读取部分。循环只在写满 n 或确认文件结束时停止,因此返回长度正是
min(n, fileLength)。
设实际写入字符数为 k。read4 调用和复制都处理常数大小块,总时间 O(k),最多还有一次返回零
的调用;临时数组固定四字符,额外空间 O(1)。这里只有一种状态设计能同时满足 API 粒度和缓冲区边界,
没有保留缺乏认知增量的第二份 C++ 实现。