博文中会简要介绍Leetcode P0158题目分析及解题思路。
“Read N Characters Given Read4 II - Call multiple times”是p0157的复杂版。这道题的难点在于如果不是一次性读完，由于read4在有充足字符的情况下一定会读取4个字符，此时若需要的字符少于4个，那么剩余的字符不能丢弃，而必须缓存在当前类实例的空间中供后续使用。
Given a file and assume that you can only read the file using a given method read4, implement a method read to read n characters. Your method read may be called multiple times.
这道题的核心思路很直接明了，通过维护一个buffer数组作为缓存来存储当前已经读取但尚未返回（使用）的字符。每次使用read来读取字符的时候，先检查缓存数组中有没有剩余，若有剩余的则先从缓存数组中提取。
以下是Java的题解代码实现。
/**
* The read4 API is defined in the parent class Reader4.
* int read4(char[] buf4);
*/
public class Solution extends Reader4 {
/**
* @param buf Destination buffer
* @param n Number of characters to read
* @return The number of actual characters read
*/
public int read(char[] buf, int n) {
// Read from local buffer
int left = this.size-this.begin, start = 0;
if (left > 0) {
int count = Math.min(left, n);
for (int idx=0; idx<count; ++idx) {
buf[idx] = this.buffer[idx+this.begin];
}
// Local buffer meet the requirement
if (count == n) {
this.begin += n;
return n;
}
start = left;
n -= left;
}
// Clear the local buffer
this.size = this.begin = 0;
int requiredRemained = n, count = -1, itr = 0, len = left;
char[] buf4 = new char[4];
while (requiredRemained >= 4) {
count = super.read4(buf4);
// No enough characters
if (count == 0)
return len;
// Copy
len += count;
for (int idx=0; idx<count; ++idx)
buf[start+itr*4+idx] = buf4[idx];
++itr;
requiredRemained -= count;
}
int actualRemained = super.read4(buf4), idx = 0;
// Min of actual remained and required remained
count = Math.min(actualRemained, requiredRemained);
for (; idx<count; ++idx)
buf[start+itr*4+idx] = buf4[idx];
// Cache the remained into the local buffer
for (; idx<actualRemained; ++idx) {
this.buffer[this.size-this.begin] = buf4[idx];
++this.size;
}
len += count;
return len;
}
private char[] buffer = new char[4];
private int begin = 0;
private int size = 0;
}
以下是C++的题解代码实现。
/**
* The read4 API is defined in the parent class Reader4.
* int read4(char *buf4);
*/
class Solution {
public:
/**
* @param buf Destination buffer
* @param n Number of characters to read
* @return The number of actual characters read
*/
int read(char *buf, int n) {
// Read from local buffer
int left = this->size_-this->begin_, start = 0;
if (left > 0) {
int count = min(left, n);
for (int idx=0; idx<count; ++idx) {
buf[idx] = this->buffer_[idx+this->begin_];
}
// Local buffer meet the requirement
if (count == n) {
this->begin_ += n;
return n;
}
start = left;
n -= left;
}
// Clear the local buffer
this->size_ = this->begin_ = 0;
int remained = n, count = -1, itr = 0, len = left;
char *buf4 = new char[4];
while (remained >= 4) {
count = read4(buf4);
// No enough characters
if (count == 0)
return len;
// Copy
len += count;
for (int idx=0; idx<count; ++idx)
buf[start+itr*4+idx] = buf4[idx];
++itr;
remained -= count;
}
int actual = read4(buf4), idx = 0;
// Min of actual remained and required remained
count = min(actual, remained);
for (; idx<count; ++idx)
buf[start+itr*4+idx] = buf4[idx];
// Cache the remained into the local buffer
for (; idx<actual; ++idx) {
this->buffer_[this->size_-this->begin_] = buf4[idx];
++this->size_;
}
len += count;
return len;
}
private:
char *buffer_ = new char[4];
int begin_ = 0;
int size_ = 0;
};