LeetCode第158题_用Read4读取N个字符 II

LeetCode 第158题：用Read4读取N个字符 II

题目形貌

给你一个文件，而且该文件只能通过给定的 read4 方法来读取，请实现一个方法来读取 n 个字符。
read4 方法：

• API read4 可以从文件中读取 4 个一连的字符，而且将它们写入缓存数组 buf 中。
  
• 返回值为实际读取的字符个数。
  

注意：read4() 有本身的文件指针，就像 C 语言中的 FILE *fp 一样。
难度

困难
题目链接

点击在LeetCode中查看题目
示例

示例 1：

1. 输入： file = "abc", n = 4
2. 输出： 3
3. 解释： 当执行你的 read 方法后，buf 需要包含 "abc"。 文件一共 3 个字符，因此返回 3。 注意 "abc" 是文件的内容，不是 buf 的内容。

复制代码

示例 2：

1. 输入： file = "abcde", n = 5
2. 输出： 5
3. 解释： 当执行你的 read 方法后，buf 需要包含 "abcde"。文件共 5 个字符，因此返回 5。

复制代码

示例 3：

1. 输入： file = "abcdABCD1234", n = 12
2. 输出： 12
3. 解释： 当执行你的 read 方法后，buf 需要包含 "abcdABCD1234"。文件一共 12 个字符，因此返回 12。

复制代码

示例 4：

1. 输入： file = "leetcode", n = 5
2. 输出： 5
3. 解释： 当执行你的 read 方法后，buf 需要包含 "leetc"。文件中一共 5 个字符，因此返回 5。

复制代码

提示

• 1 <= file.length <= 500
  
• n >= 1
  
• 你 不能 直接操纵该文件，只能通过 get 方法来获取文件内容。
  
• 请 不要 修改输出效果数组。
  
• 假定全部字符都是 ASCII 码表中的字符。
  

解题思绪

方法：队列

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

• 使用队列存储read4读取的未使用字符
  
• 当队列为空时，使用read4读取新的字符
  
• 从队列中取出字符直到到达目标字符数或队列为空
  
• 处置惩罚界限情况
  
• 返回实际读取的字符数
  

时间复杂度：O(n)，此中n是要读取的字符数。
空间复杂度：O(1)，只需要固定巨细的队列。
代码实现

C# 实现

1. public class Solution {
2.     private Queue<char> queue = new Queue<char>();
3.    
4.     public int Read(char[] buf, int n) {
5.         int total = 0;
6.         char[] temp = new char[4];
7.         
8.         while (total < n) {
9.             if (queue.Count == 0) {
10.                 int count = Read4(temp);
11.                 if (count == 0) break;
12.                
13.                 for (int i = 0; i < count; i++) {
14.                     queue.Enqueue(temp[i]);
15.                 }
16.             }
17.             
18.             if (queue.Count == 0) break;
19.             
20.             buf[total++] = queue.Dequeue();
21.         }
22.         
23.         return total;
24.     }
25. }

复制代码

Python 实现

1. class Solution:
2.     def __init__(self):
3.         self.queue = []
4.         
5.     def read(self, buf: List[str], n: int) -> int:
6.         total = 0
7.         temp = [None] * 4
8.         
9.         while total < n:
10.             if not self.queue:
11.                 count = read4(temp)
12.                 if count == 0:
13.                     break
14.                 self.queue.extend(temp[:count])
15.                
16.             if not self.queue:
17.                 break
18.                
19.             buf[total] = self.queue.pop(0)
20.             total += 1
21.             
22.         return total

复制代码

C++ 实现

1. class Solution {
2. private:
3.     queue<char> q;
4.    
5. public:
6.     int read(char *buf, int n) {
7.         int total = 0;
8.         char temp[4];
9.         
10.         while (total < n) {
11.             if (q.empty()) {
12.                 int count = read4(temp);
13.                 if (count == 0) break;
14.                
15.                 for (int i = 0; i < count; i++) {
16.                     q.push(temp[i]);
17.                 }
18.             }
19.             
20.             if (q.empty()) break;
21.             
22.             buf[total++] = q.front();
23.             q.pop();
24.         }
25.         
26.         return total;
27.     }
28. };

复制代码

性能分析

各语言实现的性能对比：
实现语言执行用时内存斲丧特点C#92 ms38.2 MB实现轻便，性能适中Python156 ms16.8 MB代码最轻便C++24 ms9.6 MB性能最优增补分析

代码亮点

• 使用队列存储未使用的字符
  
• 处置惩罚了各种界限情况
  
• 代码结构清楚，易于维护
  

常见错误

• 没有处置惩罚文件竣事的情况
  
• 没有处置惩罚n大于文件长度的情况
  
• 队列为空时的处置惩罚不妥
  

干系题目

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