Google
157 Read N Characters Given Read4

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 will only be called once for each test case.

2. Implementation

思路: 这题要我们利用一个已有的函数read4()实现一个自定义的函数read(), 和read4()不同的是,read()里有一个参数n,定义我们读多少byte的数据,而read4()只会一次读4个byte。这里主要的考点是edge cases. 如果read4返回的值是小于4,说明是end of file。同时为了保证我们读取不超过 n个byte的数据,每次将数据copy到buffer时,我们都要取n - index和size之间较小的那个数。
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
public int read(char[] buf, int n) {
11
boolean eof = false;
12
char[] buffer = new char[4];
13
int index = 0;
14
while (!eof && index < n) {
15
int size = read4(buffer);
16
if (size < 4) {
17
eof = true;
18
}
19
int bytes = Math.min(n - index, size);
20
for (int i = 0; i < bytes; i++) {
21
buf[index++] = buffer[i];
22
}
23
}
24
return index;
25
}
26
}
Copied!

3. Time & Space Complexity

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