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 码表中的字符。

解题思路

方法：队列

使用队列存储未使用的字符。
关键点：

1. 使用队列存储read4读取的未使用字符
2. 当队列为空时，使用read4读取新的字符
3. 从队列中取出字符直到达到目标字符数或队列为空
4. 处理边界情况
5. 返回实际读取的字符数

时间复杂度：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 = 0
        temp = [None] * 4
        
        while total < n:
            if not self.queue:
                count = read4(temp)
                if count == 0:
                    break
                self.queue.extend(temp[:count])
                
            if not self.queue:
                break
                
            buf[total] = self.queue.pop(0)
            total += 1
            
        return 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;
    }
};

性能分析

各语言实现的性能对比：

补充说明

代码亮点

1. 使用队列存储未使用的字符
2. 处理了各种边界情况
3. 代码结构清晰，易于维护

常见错误

1. 没有处理文件结束的情况
2. 没有处理n大于文件长度的情况
3. 队列为空时的处理不当

相关题目

• 157. 用Read4读取N个字符
• 68. 文本左右对齐
• 43. 字符串相乘