Read N Characters Given Read4 II - Call multiple times

https://leetcode.com/problems/read-n-characters-given-read4-ii-call-multiple-times/description/ https://www.lintcode.com/problem/read-n-characters-given-read4-ii-call-multiple-times/description

The API: int read4(char *buf) reads 4 characters at a time from a file.

The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file.

By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file.

Note:

The read function may be called multiple times.

Thoughts

给定read4(char *buf)能从内存中读4个字符给buf，每次调用都会从上次的结束位置往后继续读4个，当内存剩下的未读不足4个时返回本次实际读了多少个；让用read4每次能读n个字符实现read(char *buf, int n)。read4会从头覆盖buf，因此需要额外空间为4的inbuf存从read4中拿到的字符，然后把它赋值给buf。global变量write_pos记录inbuf中写入到的位置，read_pos记录inbuf读到的位置，当read_pos到达write时说明in_buf内容都已读完，重新调用read4写入inbuf并重置read_pos。

Code

// 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 inbuf[4];
    int read_pos = 0, write_pos = 0;
    int read(char *buf, int n) {
        for (int i = 0; i < n; ++i) {
            if (read_pos == write_pos) {
                write_pos = read4(inbuf);
                read_pos = 0;
                if (write_pos == 0) return i;
            }
            buf[i] = inbuf[read_pos++];
        }
        return n;
    }
};

Analysis

时间复杂度O(N).