[Leetcode] Read N Characters Given Read4 用Read4 AP

wayneli 發(fā)布于2019-08-14 12:36 / 3231人閱讀

摘要：臨時數(shù)組法復(fù)雜度時間空間思路用一個臨時數(shù)組，存放每次讀到字符，再用一個指針標記數(shù)組目前存儲到的位置，然后將這個臨時數(shù)組的內(nèi)容存到相應(yīng)的位置就行了。

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.

臨時數(shù)組法 復(fù)雜度

時間 O(N) 空間 O(1)

思路

用一個臨時數(shù)組，存放每次read4讀到字符，再用一個指針標記buf數(shù)組目前存儲到的位置，然后將這個臨時數(shù)組的內(nèi)容存到buf相應(yīng)的位置就行了。這里需要注意兩個corner case：

如果本次讀到多個字符，但是我們只需要其中一部分就能完成讀取任務(wù)時，我們要拷貝的長度是本次讀到的個數(shù)和剩余所需個數(shù)中較小的

如果read4沒有讀滿4個，說明數(shù)據(jù)已經(jīng)讀完，這時候?qū)τ谧x到的數(shù)據(jù)長度，因為也可能存在我們只需要其中一部分的情況，所以要返回總所需長度和目前已經(jīng)讀到的長度的較小的

代碼

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];
            // 將數(shù)據(jù)讀入臨時數(shù)組
            int len = read4(tmp);
            // 將臨時數(shù)組拷貝至buf數(shù)組，這里拷貝的長度是本次讀到的個數(shù)和剩余所需個數(shù)中較小的
            System.arraycopy(tmp, 0, buf, i, Math.min(len, n - i));
            // 如果讀不滿4個，說明已經(jīng)讀完了，返回總所需長度和目前已經(jīng)讀到的長度的較小的
            if(len < 4) return Math.min(i + len, n);
        }
        // 如果循環(huán)內(nèi)沒有返回，說明讀取的字符是4的倍數(shù)
        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.

隊列法 復(fù)雜度

時間 O(N) 空間 O(1)

思路

因為要調(diào)用多次，這里又多了一些corner case：

第一次調(diào)用時，如果read4讀出的多余字符我們要先將其暫存起來，這樣第二次調(diào)用時先讀取這些暫存的字符

第二次調(diào)用時，如果連暫存字符都沒讀完，那么這些暫存字符還得留給第三次調(diào)用時使用

所以，難點就在于怎么處理這個暫存字符。因為用數(shù)組和指針控制對第二種情況比較麻煩，且這些字符滿足先進先出，所以我們可以用一個隊列暫存這些字符。這樣，只要隊列不為空，就先讀取隊列。

代碼

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個，說明數(shù)據(jù)已經(jīng)讀完，返回總所需長度和目前已經(jīng)讀到的長度的較小的
            if(len < 4) return Math.min(i + len, n);
        }
        // 如果到這里，說明都是完美讀取，直接返回n
        return n;
    }
}