# Read N Characters Given Read4 II - Call multiple times `Design`, `Array`, `String` **Hard** Given a file and assume that you can only read the file using a given method `read4`, implement a method`read`to read\_n\_characters.**Your method** `read`**may be called multiple times.** **Method read4:** The API `read4`reads 4 consecutive characters from the file, then writes those characters into the buffer array`buf`. The return value is the number of actual characters read. Note that `read4()`has its own file pointer, much like`FILE *fp`in C. **Definition of read4:** ``` Parameter: char[] buf Returns: int Note: buf[] is destination not source, the results from read4 will be copied to buf[] ``` Below is a high level example of how`read4`works: ``` File file("abcdefghijk"); // File is "abcdefghijk", initially file pointer (fp) points to 'a' char[] buf = new char[4]; // Create buffer with enough space to store characters read4(buf); // read4 returns 4. Now buf = "abcd", fp points to 'e' read4(buf); // read4 returns 4. Now buf = "efgh", fp points to 'i' read4(buf); // read4 returns 3. Now buf = "ijk", fp points to end of file ``` **Method read:** By using the`read4`method, implement the method `read`that readsncharacters from the file and store it in the buffer array `buf`. Consider that you**cannot**manipulate the file directly. The return value is the number of actual characters read. **Definition of read:** ``` Parameters: char[] buf, int n Returns: int Note: buf[] is destination not source, you will need to write the results to buf[] ``` **Example 1:** ``` File file("abc"); Solution sol; // Assume buf is allocated and guaranteed to have enough space for storing all characters from the file. sol.read(buf, 1); // After calling your read method, buf should contain "a". We read a total of 1 character from the file, so return 1. sol.read(buf, 2); // Now buf should contain "bc". We read a total of 2 characters from the file, so return 2. sol.read(buf, 1); // We have reached the end of file, no more characters can be read. So return 0. ``` **Example 2:** ``` File file("abc"); Solution sol; sol.read(buf, 4); // After calling your read method, buf should contain "abc". We read a total of 3 characters from the file, so return 3. sol.read(buf, 1); // We have reached the end of file, no more characters can be read. So return 0. ``` **Note:** 1. Consider that you **cannot** manipulate the file directly, the file is only accesible for `read4` but **not** for `read`. 2. The `read` function may be called **multiple times**. 3. Please remember to **RESET** your class variables declared in Solution, as static/class variables are **persisted across multiple test cases** . Please see [here](https://leetcode.com/faq/) for more details. 4. You may assume the destination buffer array, `buf`, is guaranteed to have enough space for storing \_n \_characters. 5. It is guaranteed that in a given test case the same buffer `buf` is called by `read`. ## Analysis 是[同名问题](https://aaronice.gitbook.io/lintcode/data_structure/read-n-characters-given-read4)的follow-up。感觉上不难，但是写起来让人抓狂。感觉画图来模拟这个过程会更好。 最终代码不长，难点在于理解这个题目究竟要做什么，并且用比较好的方法来应对多次call时，前次call用了超出需要的长度，但是由于file reader只能向前，因此需要在**内部buffer**保存前次`read4()`的结果，并且处理好在内部buffer的部分未被读取、使用的部分，用于下一次call。由于这些数字的相对大小关系不确定，如何在各种情况下操作是本题的难点。 有几个变量： **ibuf** - 内部buffer，长度为`read4()`默认读取的长度，即4 **bufCount** - 代表内部临时buffer中未被复制读取过的长度，如果为0，则需要读新数据`read4()`，需重置`bufCount = read4()`， **bufEnd** - 代表上次读取`read4()`之后，数据的长度即`ibuf[bufEnd - 1]`是上次读取后`ibuf[]`中最右末尾位置的数据 **bufPtr** - 记录上次拷贝`ibuf[]`到结果`buf[]`之后，`ibuf[]`中未读（未复制或者未使用）数据的最左端位置。 **curPtr** - 记录当前已拷贝到`buf[]`中的位置，因此外层循环的条件（之一）就是curPtr < n ## Solution 根据思路实现即可。 其中 ```java // EOF if (bufCount == 0) { break; } ``` 是为了判断read4()已经读到文件尾。 **实现：** ```java /** * The read4 API is defined in the parent class Reader4. * int read4(char[] buf); */ public class Solution extends Reader4 { private int SIZE = 4; private int bufCount = 0; private int bufEnd = 0; private int bufPtr = 0; private char[] ibuf = new char[SIZE]; /** * @param buf Destination buffer * @param n Number of characters to read * @return The number of actual characters read */ public int read(char[] buf, int n) { int curPtr = 0; while (curPtr < n) { if (bufCount == 0) { bufCount = read4(ibuf); bufEnd = bufCount; bufPtr = 0; } // EOF if (bufCount == 0) { break; } while (bufPtr < bufEnd && curPtr < n) { buf[curPtr++] = ibuf[bufPtr++]; bufCount--; } } return curPtr; } } ``` **相同思路，加上EOF标记更直观** ```java /** * The read4 API is defined in the parent class Reader4. * int read4(char[] buf); */ public class Solution extends Reader4 { private int SIZE = 4; private int bufCount = 0; private int bufEnd = 0; private int bufPtr = 0; private char[] ibuf = new char[SIZE]; /** * @param buf Destination buffer * @param n Number of characters to read * @return The number of actual characters read */ public int read(char[] buf, int n) { int curPtr = 0; boolean EOF = false; while (curPtr < n && !EOF) { if (bufCount == 0) { bufCount = read4(ibuf); bufEnd = bufCount; bufPtr = 0; if (bufCount < 4) { EOF = true; } } while (bufPtr < bufEnd && curPtr < n) { buf[curPtr++] = ibuf[bufPtr++]; bufCount--; } } return curPtr; } } ``` **更简洁（短）的写法：** ```java public class Solution extends Reader4 { /** * @param buf Destination buffer * @param n Number of characters to read * @return The number of actual characters read */ private int buffPtr = 0; private int buffCnt = 0; private char[] buff = new char[4]; public int read(char[] buf, int n) { int ptr = 0; while (ptr < n) { if (buffPtr == 0) { buffCnt = read4(buff); } if (buffCnt == 0) break; while (ptr < n && buffPtr < buffCnt) { buf[ptr++] = buff[buffPtr++]; } if (buffPtr >= buffCnt) buffPtr = 0; } return ptr; } } ``` ## Reference