Saturday, January 10, 2015

Read N Characters Given Read4 (LeetCode String)

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

Idea: With two simple examples, we can understand this problem easily.
Example 1:  read 15 characters from a buffer with only 11 characters.
Run 1: read 4 characters
Run 2: read 4
Run 3: can only read 3, since there are only 3 characters left in the original data.

Example 2: read 15 characters from a buffer with 20 characters.
Run 1: read 4
Run 2: read 4
Run 3: read 4
Run 4: read 4, but only assign the first 3 to the destination buf[], since we only need to read 3 characters in this run.

So the characters read at the each run = Math.min(original data length - read in former runs==read4(buf), n-read in former runs).

Time: O(n) Space: O(1)

Code:
 /* 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 readBytes=0;  
     boolean eof=false;  
     while(readBytes<n&&eof==false)  
     {  
       char[] buffer=new char[4];  
       int read4Result=read4(buffer);  
       if(read4Result<4)  
         eof=true;  
       int actuallyRead=Math.min(n-readBytes,read4Result);  
       for(int i=0;i<actuallyRead;i++)  
         buf[readBytes+i]=buffer[i];  
       readBytes+=actuallyRead;  
     }  
     return readBytes;  
   }  
 }  

No comments:

Post a Comment