158 Read N Characters Given Read4 II - Call multiple times

158. Read N Characters Given Read4 II - Call multiple times

1. Question

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 theread4API, implement the functionint read(char *buf, int n)that readsncharacters from the file.

Note: Thereadfunction may be called multiple times.

2. Implementation

思路:

(1) 这题和157不同的是read4()可能被call很多次，这意味着之前call read4()会有一些数据保留在buffer里未读到。举个例子，比如输入数据是 s = "abcde"， 第一次我们call read(s, 1), 我们只要读a，但里面read4()实际上读"abcd", bcd还在buffer未被读取。如果我们下一次call read4(s, 4), 我们要读取"bcde",要先把buffer之前保留的数据读取。

(2) 解决方法是用一个全局数组buffer[] 保留每次read4()返回的数据，同时bufferIndex记录buffer上次读到的位置， 只有当bufferIndex等于readBytes时，之前的buffer的数据才读完。

/* The read4 API is defined in the parent class Reader4.
      int read4(char[] buf); */

public class Solution extends Reader4 {
    /**
     * @param buf Destination buffer
     * @param n   Maximum number of characters to read
     * @return    The number of characters read
     */

    int bufferIndex = 0;
    int readBytes = 0;
    char[] buffer = new char[4];

    public int read(char[] buf, int n) {
        int index = 0;

        while (index < n) {
            if (bufferIndex < readBytes) {
                buf[index++] = buffer[bufferIndex++];
            }
            else {
                readBytes = read4(buffer);
                bufferIndex = 0;
                if (readBytes == 0) {
                    break;
                }
            }
        }
        return index;
    }
}

3. Time & Space Complexity

时间复杂度O(n), 空间复杂度O(1)