[Leetcode] Read N Characters Given Read4 用Read4 AP

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

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

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ù)組法 復雜度

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

思路

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

如果本次讀到多個字符，但是我們只需要其中一部分就能完成讀取任務時，我們要拷貝的長度是本次讀到的個數(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.

隊列法 復雜度

時間 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;
    }
}

云服務器 GPU云服務器 Characters given 內(nèi)存不能為read LeetCode

文章版權歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/64582.html

[LeetCode] 158. Read N Characters Given Read4 II -

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

周國輝 2019-08-16 13:48 評論0 收藏0
158. Read N Characters Given Read4 II - Call multi

摘要：題目鏈接和那道不同的是這次，問題就是當前的可能存在多讀了幾個字節(jié)，那么下一次的時候要先算上上次多讀的部分，所以要保存上次讀的。和讀一次一樣有兩種要考慮的讀完了沒讀完，但是裝滿了 158. Read N Characters Given Read4 II - Call multiple times 題目鏈接：https://leetcode.com/problems... 和那道read...

SillyMonkey 2019-08-19 10:45 評論0 收藏0
157. Read N Characters Given Read4

摘要：題目解答讀懂題目很重要，還是要多寫寫這種實際的的問題。實際文件讀到頭了的情況需要讀的文件個數(shù)達到了的情況題目：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 exam...

crossoverJie 2019-08-14 14:16 評論0 收藏0
翻轉(zhuǎn)字符串的相關題目

摘要：一題目描述空格分隔，逐個反轉(zhuǎn)二題目描述三題目描述當然也可以用的做，不過用雙指針更快。 LeetCode: 557. Reverse Words in a String III 一、LeetCode: 557. Reverse Words in a String III 題目描述 Given a string, you need to reverse the order of chara...

lykops 2019-08-15 17:47 評論0 收藏0
[Leetcode] Isomorphic Strings 同構(gòu)字符串

摘要：最新更新思路和其他語言請訪問哈希表法復雜度時間空間思路用一個哈希表記錄字符串中字母到字符串中字母的映射關系，一個集合記錄已經(jīng)映射過的字母?；蛘哂脙蓚€哈希表記錄雙向的映射關系。這里不能只用一個哈希表，因為要排除這種多對一的映射。 Isomorphic Strings 最新更新思路和其他語言請訪問：https://yanjia.me/zh/2018/11/... Given two st...

antz 2019-08-14 12:28 評論0 收藏0