[Leetcode] Read N Characters Given Read4 用Read4 AP

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

摘要：臨時(shí)數(shù)組法復(fù)雜度時(shí)間空間思路用一個(gè)臨時(shí)數(shù)組，存放每次讀到字符，再用一個(gè)指針標(biāo)記數(shù)組目前存儲(chǔ)到的位置，然后將這個(gè)臨時(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í)數(shù)組法 復(fù)雜度

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

思路

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

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

如果read4沒(méi)有讀滿4個(gè)，說(shuō)明數(shù)據(jù)已經(jīng)讀完，這時(shí)候?qū)τ谧x到的數(shù)據(jù)長(zhǎng)度，因?yàn)橐部赡艽嬖谖覀冎恍枰渲幸徊糠值那闆r，所以要返回總所需長(zhǎng)度和目前已經(jīng)讀到的長(zhǎ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í)數(shù)組
            int len = read4(tmp);
            // 將臨時(shí)數(shù)組拷貝至buf數(shù)組，這里拷貝的長(zhǎng)度是本次讀到的個(gè)數(shù)和剩余所需個(gè)數(shù)中較小的
            System.arraycopy(tmp, 0, buf, i, Math.min(len, n - i));
            // 如果讀不滿4個(gè)，說(shuō)明已經(jīng)讀完了，返回總所需長(zhǎng)度和目前已經(jīng)讀到的長(zhǎng)度的較小的
            if(len < 4) return Math.min(i + len, n);
        }
        // 如果循環(huán)內(nèi)沒(méi)有返回，說(shuō)明讀取的字符是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.

隊(duì)列法 復(fù)雜度

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

思路

因?yàn)橐{(diào)用多次，這里又多了一些corner case：

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

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

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

代碼

public class Solution extends Reader4 {
    Queue remain = new LinkedList();
    
    public int read(char[] buf, int n) {
        int i = 0;
        // 隊(duì)列不為空時(shí)，先讀取隊(duì)列中的暫存字符
        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);
                // 把多余的字符存入隊(duì)列中
                for(int j = n - i; j < len; j++){
                    remain.offer(tmp[j]);
                }
            // 如果讀到的字符少于我們需要的字符，直接拷貝
            } else {
                System.arraycopy(tmp, 0, buf, i, len);
            }
            // 同樣的，如果讀不滿4個(gè)，說(shuō)明數(shù)據(jù)已經(jīng)讀完，返回總所需長(zhǎng)度和目前已經(jīng)讀到的長(zhǎng)度的較小的
            if(len < 4) return Math.min(i + len, n);
        }
        // 如果到這里，說(shuō)明都是完美讀取，直接返回n
        return n;
    }
}