Massive Algorithms: LeetCode 158 - Read N Characters Given Read4 II

LeetCode 158 - Read N Characters Given Read4 II

LeetCode 157 - Read N Characters Given Read4
https://cheonhyangzhang.wordpress.com/2016/12/22/158-leetcode-java-read-n-characters-given-read4-ii-call-multiple-times-add-to-list-questioneditorial-solution-hard/

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.

The difference between this question and the first version is that the read() function will be called multiple times.
The trouble here will be as the following example if using the first version solution:
file: “abcdefg”
read(3) read(2) read(2) should be “abc” “de” “fg”
but using first version solution it will print “abc” “ef” “”

This is because when you use read4() to read, the pointer to read file has already moved to “e” after the first call of read4(). So it’s not correct any more.

In order to solve, we need to persist the characters that has been already read by using read4 but it’s not put into the result of read().

In the solution below, I am using a buf4[] to store the characters read by using read4 and also a buf4Size and buf4Index to keep track of the size of the buf4 and the next character to use in buf4[].

[LeetCode] Read N Characters Given Read4 II | 程序员达达
[分析]
跟之前的一道题目比，这一题要复杂不少。主要是因为read函数可以调用多次以后，有可能文件中的部分内容被读出来，但是暂时没有用到。因此需要额外的空间来缓存读出来的字符。
[注意事项]
1）对于几个变量的解读：
－ buffer 存储从文件中读出来的字符
－ offset 上一次读取之后buffer中剩下字符的偏移量
－ bufsize buffer中剩下字符的个数

https://discuss.leetcode.com/topic/6402/clean-accepted-java-solution

    private int offSet = 0;
    private int remaining = 0;
    private boolean isEndOfFile = false;
    private char[] buffer = new char[4];
    public int read(char[] buf, int n) {
        int readBytes = 0;
        while (readBytes < n && (remaining != 0 || !isEndOfFile)) {
            int readSize = 0;
            if (remaining != 0) {
                readSize = remaining;
            } else {
                offSet = 0;
                readSize = read4(buffer);
                if (readSize != 4) {
                    isEndOfFile = true;
                }
            }
            int length = Math.min(n - readBytes, readSize);
            for (int i= offSet; i<offSet + length; i++) {
                buf[readBytes++] = buffer[i];
            }
            remaining = readSize - length;
            if (remaining != 0) {
                offSet += length;
            }
        }
        return readBytes;
    }

http://yuanhsh.iteye.com/blog/2186426

private char[] buffer = new char[4];
private int offset = 0, bufsize = 0;
public int read(char[] buf, int n) {
int total = 0;
boolean eof = false;
while (!eof && total < n) {
if (bufsize == 0) {
bufsize = read4(buffer);
if (bufsize < 4) {
eof = true;
}
}
int bytes = Math.min(n - total, bufsize);
System.arraycopy(buffer /*src*/, offset /*srcPos*/,
buf /*dest*/, total /*destPos*/,
bytes /*length*/);
offset = (offset + bytes) % 4;
bufsize -= bytes;
total += bytes;
}
return total;
}

   private char [] buffer = new char[4];
   int offset = 0, bufsize = 0; 
   public int read(char[] buf, int n) {
      int readBytes = 0;
      boolean eof = false;
      while (!eof && readBytes < n) {
          int sz = (bufsize>0)? bufsize : read4(buffer);
          if (bufsie==0 && sz < 4) eof = true;
          int bytes = Math.min(n - readBytes, sz); 
          System.arraycopy(buffer /* src */, offset /* srcPos */, buf /* dest */,

                 readBytes /* destPos */, bytes /* length */);
          offset = (offset + bytes) % 4;
          bufsize = sz - bytes;
          readBytes += bytes;
    }
      return readBytes;
   }

https://leetcode.com/discuss/19581/clean-accepted-java-solution

The key is to store memorized variable in the class level and remember offset position and remaining number of elements.

private int offSet = 0; private int remaining = 0; private boolean isEndOfFile = false; private char[] buffer = new char[4]; public int read(char[] buf, int n) { int readBytes = 0; while (readBytes < n && (remaining != 0 || !isEndOfFile)) { int readSize = 0; if (remaining != 0) { readSize = remaining; } else { offSet = 0; readSize = read4(buffer); if (readSize != 4) { isEndOfFile = true; } } int length = Math.min(n - readBytes, readSize); for (int i= offSet; i<offSet + length; i++) { buf[readBytes++] = buffer[i]; } remaining = readSize - length; if (remaining != 0) { offSet += length; } } return readBytes; }
https://leetcode.com/discuss/40768/java-solution-no-if-s

public class Solution extends Reader4 {
    private char[] buffer = new char[4];
    private int bufferBytes = 0;
    private int bufferPointer = 0;

    public int read(char[] buf, int n) {
        int copy = Math.min(n, bufferBytes);
        System.arraycopy(buffer, bufferPointer, buf, 0, copy);
        bufferBytes -= copy;
        bufferPointer += copy;

        int total = copy;
        int readBytes = 4;
        while (total < n && readBytes == 4) {
            readBytes = read4(buffer);
            copy = Math.min(n-total, readBytes);
            bufferBytes = readBytes - copy;
            bufferPointer = copy;
            System.arraycopy(buffer, 0, buf, total, copy);
            total += copy;
        }

        return total;
    }
}

copying data from the buffer;
copying data from the underlying stream;
maintain bufferPointer/bufferBytes in the both sections. No if(s).

http://www.cnblogs.com/EdwardLiu/p/4240616.html

其实我觉得可以只用一个offset作为instance variable，而不用再用一个oneRead, 因为offset+oneRead = 4

X. Use Queue
https://leetcode.com/discuss/22982/java-solution-with-clean-comments

Use a queue to store the character being left by last read. And first check the queue before a new read

private Queue<Character> lastLeft = new LinkedList<Character>(); public int read(char[] buf, int n){ int i = 0; int bufferLength = 0, readLength = 4; char[] buffer = new char[4]; // pop the last left characters first while(i < n && !lastLeft.isEmpty()){ buf[i++] = lastLeft.poll(); } // read in new characters while(i < n){ if(bufferLength==0){ bufferLength = read4(buffer); readLength = bufferLength; } buf[i++] = buffer[readLength-(bufferLength--)]; if(readLength < 4 && bufferLength==0) return i; } // push the remaining into queue for next use while(bufferLength!=0){ queue.add(buffer[bufferLength--]); } return i; }
http://segmentfault.com/a/1190000003794420

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

第一次调用时，如果read4读出的多余字符我们要先将其暂存起来，这样第二次调用时先读取这些暂存的字符
第二次调用时，如果连暂存字符都没读完，那么这些暂存字符还得留给第三次调用时使用

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

    Queue<Character> remain = new LinkedList<Character>();
    
    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;
    }

https://changhaz.wordpress.com/2014/11/24/leetcode-read-n-characters-given-read4-ii-call-multiple-times/
Related LeetCode 157 - Read N Characters Given Read4
Read full article from [LeetCode] Read N Characters Given Read4 II | 程序员达达

LeetCode 158 - Read N Characters Given Read4 II

Labels

Popular Posts