0157. Read N Characters Given Read4
===================================
题目信息
--------
:题号: 0157. 用 Read4 读取 N 个字符
:难度: Easy
:主题: 字符串、缓冲区、外部 API、边界控制
:原题: `LeetCode 0157 `_
:重点: 用四字符临时块隔离 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++ 实现
--------
.. code-block:: cpp
// 平台已提供:int read4(char* buf4);
#include
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``;返回状态
只能增加一。
.. list-table::
:header-rows: 1
* - 文件与目标状态
- ``available``
- ``toCopy``
- ``copied`` 变化
* - ``leetcode``,目标还差五个
- ``4``,块为 ``leet``
- ``4``
- ``0 -> 4``
* - 文件继续为 ``code``,目标还差一个
- ``4``
- ``1``
- ``4 -> 5``,循环因达到 ``n`` 结束
* - 文件 ``abc``,目标还差五个
- ``3``
- ``3``
- ``0 -> 3``,确认文件末尾
两个停止条件对应两种完成原因
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
外层条件 ``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++ 实现。