[Leetcode] Read N Characters Given Read4 用Read4 AP

wayneli 发布于2019-08-14 12:36 / 2847人阅读

摘要：临时数组法复杂度时间空间思路用一个临时数组，存放每次读到字符，再用一个指针标记数组目前存储到的位置，然后将这个临时数组的内容存到相应的位置就行了。

Read N Characters Given Read4 I

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.

临时数组法 复杂度

时间 O(N) 空间 O(1)

思路

用一个临时数组，存放每次read4读到字符，再用一个指针标记buf数组目前存储到的位置，然后将这个临时数组的内容存到buf相应的位置就行了。这里需要注意两个corner case：

如果本次读到多个字符，但是我们只需要其中一部分就能完成读取任务时，我们要拷贝的长度是本次读到的个数和剩余所需个数中较小的

如果read4没有读满4个，说明数据已经读完，这时候对于读到的数据长度，因为也可能存在我们只需要其中一部分的情况，所以要返回总所需长度和目前已经读到的长度的较小的

代码

public class Solution extends Reader4 {
    public int read(char[] buf, int n) {
        for(int i = 0; i < n; i += 4){
            char[] tmp = new char[4];
            // 将数据读入临时数组
            int len = read4(tmp);
            // 将临时数组拷贝至buf数组，这里拷贝的长度是本次读到的个数和剩余所需个数中较小的
            System.arraycopy(tmp, 0, buf, i, Math.min(len, n - i));
            // 如果读不满4个，说明已经读完了，返回总所需长度和目前已经读到的长度的较小的
            if(len < 4) return Math.min(i + len, n);
        }
        // 如果循环内没有返回，说明读取的字符是4的倍数
        return n;
    }
}

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.

队列法 复杂度

时间 O(N) 空间 O(1)

思路

因为要调用多次，这里又多了一些corner case：

第一次调用时，如果read4读出的多余字符我们要先将其暂存起来，这样第二次调用时先读取这些暂存的字符

第二次调用时，如果连暂存字符都没读完，那么这些暂存字符还得留给第三次调用时使用

所以，难点就在于怎么处理这个暂存字符。因为用数组和指针控制对第二种情况比较麻烦，且这些字符满足先进先出，所以我们可以用一个队列暂存这些字符。这样，只要队列不为空，就先读取队列。

代码

public class Solution extends Reader4 {
    Queue remain = new LinkedList();
    
    public int read(char[] buf, int n) {
        int i = 0;
        // 队列不为空时，先读取队列中的暂存字符
        while(i < n && !remain.isEmpty()){
            buf[i] = remain.poll();
            i++;
        }
        for(; i < n; i += 4){
            char[] tmp = new char[4];
            int len = read4(tmp);
            // 如果读到字符多于我们需要的字符，需要暂存这些多余字符
            if(len > n - i){
                System.arraycopy(tmp, 0, buf, i, n - i);
                // 把多余的字符存入队列中
                for(int j = n - i; j < len; j++){
                    remain.offer(tmp[j]);
                }
            // 如果读到的字符少于我们需要的字符，直接拷贝
            } else {
                System.arraycopy(tmp, 0, buf, i, len);
            }
            // 同样的，如果读不满4个，说明数据已经读完，返回总所需长度和目前已经读到的长度的较小的
            if(len < 4) return Math.min(i + len, n);
        }
        // 如果到这里，说明都是完美读取，直接返回n
        return n;
    }
}

超融合服务器 idc机房托管 Characters given 内存不能为read LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64582.html

[LeetCode] 158. Read N Characters Given Read4 II -

Problem 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 i...

周国辉 2019-08-16 13:48 评论0 收藏0
158. Read N Characters Given Read4 II - Call multi

摘要：题目链接和那道不同的是这次，问题就是当前的可能存在多读了几个字节，那么下一次的时候要先算上上次多读的部分，所以要保存上次读的。和读一次一样有两种要考虑的读完了没读完，但是装满了 158. Read N Characters Given Read4 II - Call multiple times 题目链接：https://leetcode.com/problems... 和那道read...

SillyMonkey 2019-08-19 10:45 评论0 收藏0
157. 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 exam...

crossoverJie 2019-08-14 14:16 评论0 收藏0
翻转字符串的相关题目

摘要：一题目描述空格分隔，逐个反转二题目描述三题目描述当然也可以用的做，不过用双指针更快。 LeetCode: 557. Reverse Words in a String III 一、LeetCode: 557. Reverse Words in a String III 题目描述 Given a string, you need to reverse the order of chara...

lykops 2019-08-15 17:47 评论0 收藏0
[Leetcode] Isomorphic Strings 同构字符串

摘要：最新更新思路和其他语言请访问哈希表法复杂度时间空间思路用一个哈希表记录字符串中字母到字符串中字母的映射关系，一个集合记录已经映射过的字母。或者用两个哈希表记录双向的映射关系。这里不能只用一个哈希表，因为要排除这种多对一的映射。 Isomorphic Strings 最新更新思路和其他语言请访问：https://yanjia.me/zh/2018/11/... Given two st...

antz 2019-08-14 12:28 评论0 收藏0