158. Read N Characters Given Read4 II Call multiple times - cocoder39/coco39_LC GitHub Wiki

158. Read N Characters Given Read4 II - Call multiple times

Notes 2021:

deque is a good choice here

class Solution:
    def __init__(self):
        self.deque = collections.deque()
    
    def read(self, buf: List[str], n: int) -> int:
        has_read = 0
        
        # step 1: fulfill the request using internal_buf
        while self.deque and has_read < n:
            buf[has_read] = self.deque.popleft()
            has_read += 1
            
        # step 2: fulfill the request using read4
        read_from_read4 = 4
        buf4 = [' '] * 4
        while has_read < n and read_from_read4 == 4:
            read_from_read4 = read4(buf4)
            for i in range(read_from_read4):
                if has_read == n:
                    self.deque.append(buf4[i])
                else:
                    buf[has_read] = buf4[i]
                    has_read += 1
                
        return has_read

=======================================================================

Think that you have 4 chars "a, b, c, d" in the file, and you want to call your function twice like this:

read(buf, 1); // should return 'a'
read(buf, 3); // should return 'b, c, d'

All the 4 chars will be consumed in the first call. So the tricky part of this question is how can you preserve the remaining 'b, c, d' to the second call.

Maintain a queue buffer of size n. If there is date has been read out from file but not used by user, the data would be still in the buffer. Appending new data to buffer until reach EOF or read out n chars.

space complexity is O(n)

class Solution {
public:
    /**
     * @param buf Destination buffer
     * @param n   Maximum number of characters to read
     * @return    The number of characters read
     */
    int read(char *buf, int n) {
    /*
        int res = 0;
        while (res < n) {
            int cur = read4(buf);
            res += cur;
            buf += cur;
            if (cur < 4)    break;
        }
        return min(res, n);
     */   
        char *tmp = new char[4];
        while (buf1.size() < n) {
            int cur = read4(tmp);
            for (int i = 0; i < cur; i++)   buf1.push(tmp[i]);
            if (cur < 4)    break;
        }
        
        int res = min((int)buf1.size(), n); //works for two ints
        for (int i = 0; i < res; i++) {
            buf[i] = buf1.front();
            buf1.pop();
        }
        delete tmp;
        return res;
    }
private:
    queue<char> buf1;
};

O(1) extra memory

class Solution {
public:
    /**
     * @param buf Destination buffer
     * @param n   Maximum number of characters to read
     * @return    The number of characters read
     */
    int read(char *buf, int n) {
        int i = 0;
        while (i < n) {
            if (start < end) {
                buf[i++] = buf1[start++];
            } else { //readPos == writePos
                start = 0;
                end = read4(buf1);
                if (end == 0)  break; //ATTENTION!
            }
        }
        return i;
    }
private:
    char buf1[4];
    int start = 0, end = 0;
};
⚠️ **GitHub.com Fallback** ⚠️