题目描述

给定API：int read4(char *buf) 从文件中读取4个字符。
返回值是实际读到的字符数量。例如，如果返回3，则说明文件中只有3个字符。

请使用read4 API实现一个新的函数：int read(char *buf, int n) 从文件中读取 $n$ 个字符。

注意：read函数可能被调用多次。

样例1

给定 buf = "abc"
read("abc", 1) // 返回 "a"
read("abc", 2); // 返回 "bc"
read("abc", 1); // 返回 ""

样例2

给定 buf = "abc"
read("abc", 4) // 返回 "abc"
read("abc", 1); // 返回 ""

算法

(模拟) $O(n)$

由于函数会被调用多次，所以我们需要创建一个缓冲区，用来缓存之前读了但没用到的字符。

每次调用函数时，先从缓冲区读字符，如果不够再用read4函数读字符。然后将read4读的多余的字符重新存入缓冲区。

时间复杂度分析：最多读取 $n+3$ 个字符，所以时间复杂度是 $O(n)$。

C++ 代码

// Forward declaration of the read4 API.
int read4(char *buf);

class Solution {
public:
    /**
     * @param buf Destination buffer
     * @param n   Maximum number of characters to read
     * @return    The number of characters read
     */
    char cbuf[4];
    int cn = 0;

    int read(char *buf, int n) {
        if (n <= cn)
        {
            for (int i = 0; i < n; i++)
                buf[i] = cbuf[i];
            for (int i = 0, j = n; j < cn; i++, j++)
                cbuf[i] = cbuf[j];
            cn -= n;
            return n;
        }

        int s = cn;
        char *p = buf;
        for (int i = 0; i < cn; i ++ )
            *p ++ = cbuf[i];
        cn = 0;
        while (s < n)
        {
            int t = read4(cbuf), i;
            for (i = 0; i < t && s < n; i ++ )
            {
                *p++ = cbuf[i];
                s++;
            }
            if (i < t)
            {
                for (cn = 0; i + cn < t; cn ++ )
                    cbuf[cn] = cbuf[i + cn];
            }
            if (t < 4) break;
        }
        buf[s] = 0;
        return s;
    }
};