发布于 2016-01-12 02:45:09 | 320 次阅读 | 评论: 0 | 来源: PHPERZ

这里有新鲜出炉的精品教程，程序狗速度看过来！

Leetcode 在线编程网站

leetcode 是一个美国的在线编程网站，上面主要收集了各大IT公司的笔试面试题，对于应届毕业生找工作是一个不可多得的好帮手。

---

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.

分析

这道题没什么特殊的算法跟数据结构，注意越界就可以了。至于越界主要包含两种情况，一是读到文件结尾，没得读了。而是还没读到文件结尾，但是已经达到要求的n个字符了，此时应该停止继续读。处理好这两种情况即可。

这道题Follow up可以是多次读，也是LeetCode原题，即Read N Characters Given Read4 II - Call multiple times, 具体见后文。

复杂度

time: O(n), space: O(1)

代码

/* 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
     */
    public int read(char[] buf, int n) {
        int i = 0;
        char[] buffer = new char[4];
        while (i < n) {
            int bufCount = read4(buffer);
            int j = 0;
            while (j < bufCount && i < n) {
                buf[i++] = buffer[j++];
            }
            if (bufCount != 4)
                break;
        }
        return i;
    }
}

Read N Characters Given Read4 II - Call multiple times

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 may be called multiple times.

分析

多次读与一次读的主要不同在于read4()函数中的buffer相当于global的，每次read()的时候前面read4()里读进buffer的剩下来字符的还要继续用，不够才又调用read4()往buffer里新增加内容供read读取。

所以我们只要存一个global的针对read4()的buffer的起始位置和终止位置即可。每次read()先读上次buffer里没读完的字符，不够才又调用read4(). 当然，越界问题还是得注意，跟上一道题一样。

复杂度

time: O(n), space: O(1)

代码

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

public class Solution extends Reader4 {
    char[] buffer = new char[4];
    int start = 0; // inclusive
    int end = 0; // exclusive
    /**
     *@param buf Destination buffer
     *@param n   Maximum number of characters to read
     *@return    The number of characters read
     */
    public int read(char[] buf, int n) {
        int i = 0;
        while (i < n) {
            
            // 之前read4()读进buffer里的字符已全部读完
            if (start == end) {
                end = read4(buffer);
                start = 0;
            }
            
            // 依次把buffer里的字符读进buf里
            while (i < n && start < end) {
                buf[i++] = buffer[start++];
            }
            
            // 判断是否到达文件末尾，是的话跳出循环
            if (end != 4)
                break;
        }
        return i;
    }
}