题目描述
给定一个只能调用 read4 方法的类 Solution，该方法会从文件中读取 4 个字符，直到文件末尾。实现一个方法 read，该方法可以接受一个参数 n，使用 read4 方法读取 n 个字符，并以字符串的形式返回这些字符。
示例
说明：
● read4() 返回以 null 结尾的字符数组 array，最后一个可能不是 null 的字符是文件末尾的字符。
● read4() 保证在调用 read 方法时文件末尾最多有 4 个字符剩余。
示例 1:
输入: n = 5
输出: "Hello"
解释: 先读取了 4 个字符 "Hell"，再读取 1 个字符 "o"。
示例 2:
输入: n = 12
输出: "HelloWorld"
解释: 先读取了 4 个字符 "Hell"，再读取 4 个字符 "oWor"，最后读取 4 个字符 "ld"，然后组合起来就是 "HelloWorld"。
题解
这个问题可以通过模拟读取文件的过程来解决。我们可以使用一个缓存来存储 read4 方法读取的字符，然后从缓存中读取所需的字符。
- 初始化：创建一个缓存数组 buffer 来存储 read4 方法读取的字符，以及一个指针 ptr 来记录缓存中已读取的位置。
- 读取字符：当调用 read 方法时，从缓存中读取字符，直到读取了 n 个字符或缓存中没有更多的字符。
- 调用 read4：如果缓存中没有足够的字符，调用 read4 方法填充缓存，直到缓存中有足够的字符或到达文件末尾。
- 返回结果：将读取的字符组合成字符串并返回。
代码实现
class Solution {
private:vector<char> buffer;int ptr;const int read4(vector<char>& buffer) {// 模拟 read4 方法，这里需要根据实际情况实现// 为了简化，假设每次调用 read4 方法都能读取 4 个字符for (int i = 0; i < 4; ++i) {buffer.push_back('A' + (i + ptr) % 26);}ptr += 4;return 4;}public:Solution() {ptr = 0;buffer.resize(4);}string read(int n) {string result;while (result.size() < static_cast<size_t>(n)) {int size = read4(buffer);int end = size > n - result.size() ? n - result.size() : size;result.append(buffer.begin(), buffer.begin() + end);if (size == 0) break; // 到达文件末尾}return result;}
};
复杂度分析
● 时间复杂度：O(n)，其中 n 是需要读取的字符数。我们需要读取每个字符一次。
● 空间复杂度：O(1)，因为我们只使用了固定大小的缓存。
这个算法的优势在于它模拟了文件读取的过程，并且能够高效地处理读取请求。