Google
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的数据才读完。
1
/* The read4 API is defined in the parent class Reader4.
2
int read4(char[] buf); */
3
4
public class Solution extends Reader4 {
5
/**
6
* @param buf Destination buffer
7
* @param n Maximum number of characters to read
8
* @return The number of characters read
9
*/
10
11
int bufferIndex = 0;
12
int readBytes = 0;
13
char[] buffer = new char[4];
14
15
public int read(char[] buf, int n) {
16
int index = 0;
17
18
while (index < n) {
19
if (bufferIndex < readBytes) {
20
buf[index++] = buffer[bufferIndex++];
21
}
22
else {
23
readBytes = read4(buffer);
24
bufferIndex = 0;
25
if (readBytes == 0) {
26
break;
27
}
28
}
29
}
30
return index;
31
}
32
}
Copied!

3. Time & Space Complexity

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