Tuesday, January 17, 2017

Leetcode/F家 -- 157.158. Read N Characters Given Read4 I/ II - Call multiple times (Design)

157.158 Read N Characters Given Read4  I/ II - Call multiple times (Design)
easy hard
https://leetcode.com/problems/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.
思路: 理解-read4(buf) pass进去一个4格子的Array buff,将其填入file中的内容,返回读了4个还是<4个字。读过就算过了这字,下次从剩余的字读起。我们要把buff里面的值赋给buf
           设计read function从file读取n个char。
           关键点是: 最后不满4个数需要读取时,取(file剩余字符)和(剩余需读字符)中较小的值
Complexity: O(n) time
Ex: "ab" read(1): "a"

public class Solution extends Reader4 {
    /**
     * @param buf Destination buffer
     * @param n   Maximum number of characters to read
     * @return    The number of characters read
     */
    char[] buff = new char[4];
    int count = 0;//count from read4 [0,4]
    public int read(char[] buf, int n) {
        int total = 0;//total bytes have read
        while(n > 0){
            count = read4(buff);
            count = Math.min(n, count);
            for(int i = 0; i < count; i++){
                buf[total++] = buff[i];
            }
            if(count < 4)break;
            n -= 4;
        }
        return total;
    }
}

158. call read multiple times

class instance variable概念,obj的var 是keep住的
eg "abcde" [read(1) ,read(4)] - > ["a","bcde"] buffPrt: 0,1; buffCN: 4,4

思路: 在buff有剩余unread cell时(count > n)会考虑, 需要多2个变量,
           pos记录上次剩余未读的buff cell数量,index是第一个未读数的位置(其实就算count)
           在开始read4()之前,先把上一次left over 的buff assign 给buf。 注意每次loop前依旧和n比较,取小值。
ex: "ab"[read(0),read(1),read(2),read(1)] result["","a","b",""]

public class Solution extends Reader4 {
    /**
     * @param buf Destination buffer
     * @param n   Maximum number of characters to read
     * @return    The number of characters read
     */
    char[] buff = new char[4];
    int count = 0;//count from read4 [0,4]
    int pos = 0;//record left number of unused cell in buff
    int leftcnt = 0;//the index of unsed cell in buff
    int index = 0;//index of unsed cell in buff
    public int read(char[] buf, int n) {
        int total = 0;//total bytes have read
        /*fill the left over in buff first*/
        int pre = Math.min(n, leftcnt);
        for(int i = 0; i < pre; i++){
            buf[total++] = buff[index++];
            n--;
            leftcnt--;
        }
        while(n > 0){
            count = read4(buff);
            if(count > n){
                leftcnt = count - n;//unused cells
                index = n;//the index of unread cells in buff
                count = n;
            }else{
                leftcnt = 0;//all buff cells used
            }
            for(int i = 0; i < count; i++){
                buf[total++] = buff[i];
            }
            if(count < 4)break;
            n -= 4;
        }
        return total;
    }
}

No comments:

Post a Comment