Thursday, November 20, 2014

[LeetCode新题] Read N Characters Given Read4

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

思路:

由于每次只能读进4个字符,而n未必是4的倍数。所以一直读到len+4>n时停止。剩下m = n-len < 4 个字符。建立一个新的缓存remain读入4个字符,然后将其中的m个写入buff尾部。要注意在整个读入过程中的每个阶段判断是否已经读完文件。



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 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
     */
    int read(char *buf, int n) {
        int len = 0;
        int m = INT_MAX;
        while(len+4<=n) {
            m = read4(buf+len);
            len += m;
            if(m<4) break;
        }
        if(len==n || m<4) return len;

        char *remain = new char[5];
        m = min(read4(remain),n-len);
        for(int i=0; i<m; i++) buf[len++] = remain[i];
        delete remain;
        
        return len;
    }
};

3 comments:

  1. HI May I ask two questions?

    char *remain = new char[5]; // why 5?
    m = min(read4(remain),n-len); // why are you doing this?

    ReplyDelete
  2. 请问怎么分析时间复杂度呢?

    ReplyDelete