LeetCode第158題_用Read4讀取N個字符 II

LeetCode 第158題：用Read4讀取N個字符 II

題目描述

給你一個文件，并且該文件只能通過給定的 read4 方法來讀取，請實現一個方法來讀取 n 個字符。

read4 方法：

API read4 可以從文件中讀取 4 個連續的字符，并且將它們寫入緩存數組 buf 中。
返回值為實際讀取的字符個數。

注意：read4() 有自己的文件指針，就像 C 語言中的 FILE *fp 一樣。

難度

困難

題目鏈接

點擊在LeetCode中查看題目

示例

示例 1：

輸入： file = "abc", n = 4
輸出： 3
解釋： 當執行你的 read 方法后，buf 需要包含 "abc"。 文件一共 3 個字符，因此返回 3。 注意 "abc" 是文件的內容，不是 buf 的內容。

示例 2：

輸入： file = "abcde", n = 5
輸出： 5
解釋： 當執行你的 read 方法后，buf 需要包含 "abcde"。文件共 5 個字符，因此返回 5。

示例 3：

輸入： file = "abcdABCD1234", n = 12
輸出： 12
解釋： 當執行你的 read 方法后，buf 需要包含 "abcdABCD1234"。文件一共 12 個字符，因此返回 12。

示例 4：

輸入： file = "leetcode", n = 5
輸出： 5
解釋： 當執行你的 read 方法后，buf 需要包含 "leetc"。文件中一共 5 個字符，因此返回 5。

提示

1 <= file.length <= 500
n >= 1
你不能直接操作該文件，只能通過 get 方法來獲取文件內容。
請不要修改輸出結果數組。
假定所有字符都是 ASCII 碼表中的字符。

解題思路

方法：隊列

使用隊列存儲未使用的字符。
關鍵點：

使用隊列存儲read4讀取的未使用字符
當隊列為空時，使用read4讀取新的字符
從隊列中取出字符直到達到目標字符數或隊列為空
處理邊界情況
返回實際讀取的字符數

時間復雜度：O(n)，其中n是要讀取的字符數。
空間復雜度：O(1)，只需要固定大小的隊列。

代碼實現

C# 實現

public class Solution {private Queue<char> queue = new Queue<char>();public int Read(char[] buf, int n) {int total = 0;char[] temp = new char[4];while (total < n) {if (queue.Count == 0) {int count = Read4(temp);if (count == 0) break;for (int i = 0; i < count; i++) {queue.Enqueue(temp[i]);}}if (queue.Count == 0) break;buf[total++] = queue.Dequeue();}return total;}
}

Python 實現

class Solution:def __init__(self):self.queue = []def read(self, buf: List[str], n: int) -> int:total = 0temp = [None] * 4while total < n:if not self.queue:count = read4(temp)if count == 0:breakself.queue.extend(temp[:count])if not self.queue:breakbuf[total] = self.queue.pop(0)total += 1return total

C++ 實現

class Solution {
private:queue<char> q;public:int read(char *buf, int n) {int total = 0;char temp[4];while (total < n) {if (q.empty()) {int count = read4(temp);if (count == 0) break;for (int i = 0; i < count; i++) {q.push(temp[i]);}}if (q.empty()) break;buf[total++] = q.front();q.pop();}return total;}
};