0157. Read N Characters Given Read4

题目信息

题号:
  1. 用 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++ 实现

// 平台已提供: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;返回状态 只能增加一。

文件与目标状态

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++ 实现。