LeetCode 158: Read N Characters Given read4 II - Call Multiple Times (Persistent Buffer Carry-Over)
LeetCode 158StringDesignBufferToday we solve LeetCode 158 - Read N Characters Given read4 II - Call Multiple Times.
Source: https://leetcode.com/problems/read-n-characters-given-read4-ii-call-multiple-times/
English
Problem Summary
You are given an API read4(buf4) that reads up to 4 chars from a file. Implement read(buf, n) which may be called multiple times, and each call should return exactly as many chars as possible up to n.
Key Insight
Because read() is called repeatedly, extra characters fetched by read4() in one call must be saved for later calls. So we keep a persistent internal queue/buffer plus read/write pointers (or count).
Algorithm
1) While output has fewer than n chars:
2) If internal buffer is empty, call read4(tmp) and refill it.
3) If read4 returns 0, EOF reached, stop.
4) Move chars from internal buffer to user buffer until either n is satisfied or internal buffer becomes empty.
Complexity
Time: O(n) per call (amortized across moved chars).
Space: O(1) extra (fixed-size internal array of 4).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
/**
* The read4 API is defined in the parent class Reader4.
* int read4(char[] buf4);
*/
public class Solution extends Reader4 {
private final char[] buf4 = new char[4];
private int ptr = 0;
private int cnt = 0;
public int read(char[] buf, int n) {
int i = 0;
while (i < n) {
if (ptr == cnt) {
cnt = read4(buf4);
ptr = 0;
if (cnt == 0) break;
}
while (i < n && ptr < cnt) {
buf[i++] = buf4[ptr++];
}
}
return i;
}
}// read4 is provided by the platform.
// func read4(buf4 []byte) int
type Solution struct {
buf4 [4]byte
ptr int
cnt int
}
func Constructor() Solution {
return Solution{}
}
func (s *Solution) Read(buf []byte, n int) int {
i := 0
for i < n {
if s.ptr == s.cnt {
s.cnt = read4(s.buf4[:])
s.ptr = 0
if s.cnt == 0 {
break
}
}
for i < n && s.ptr < s.cnt {
buf[i] = s.buf4[s.ptr]
i++
s.ptr++
}
}
return i
}// The read4 API is defined in the parent class Reader4.
// int read4(char *buf4);
class Solution : public Reader4 {
private:
char buf4_[4];
int ptr_ = 0;
int cnt_ = 0;
public:
int read(char *buf, int n) {
int i = 0;
while (i < n) {
if (ptr_ == cnt_) {
cnt_ = read4(buf4_);
ptr_ = 0;
if (cnt_ == 0) break;
}
while (i < n && ptr_ < cnt_) {
buf[i++] = buf4_[ptr_++];
}
}
return i;
}
};# The read4 API is already defined for you.
# def read4(buf4: List[str]) -> int:
class Solution:
def __init__(self):
self.buf4 = [''] * 4
self.ptr = 0
self.cnt = 0
def read(self, buf: List[str], n: int) -> int:
i = 0
while i < n:
if self.ptr == self.cnt:
self.cnt = read4(self.buf4)
self.ptr = 0
if self.cnt == 0:
break
while i < n and self.ptr < self.cnt:
buf[i] = self.buf4[self.ptr]
i += 1
self.ptr += 1
return i/**
* @param {function} read4
* @return {function}
*/
var solution = function(read4) {
const cache = new Array(4);
let ptr = 0;
let cnt = 0;
/**
* @param {character[]} buf
* @param {number} n
* @return {number}
*/
return function(buf, n) {
let i = 0;
while (i < n) {
if (ptr === cnt) {
cnt = read4(cache);
ptr = 0;
if (cnt === 0) break;
}
while (i < n && ptr < cnt) {
buf[i++] = cache[ptr++];
}
}
return i;
};
};中文
题目概述
给定系统 API read4(buf4)，每次最多读取 4 个字符。请实现 read(buf, n)，并且 read 会被多次调用，每次都要尽量返回最多 n 个字符。
核心思路
关键点在于“多次调用”：某次调用里 read4 多读出来但当前用不完的字符，必须缓存到对象成员中，留给下一次 read 使用。否则会丢字符，结果错误。
算法步骤
1）当已输出字符数小于 n 时循环：
2）若内部缓冲已空，调用 read4 重新填充。
3）若返回 0，说明到达文件末尾，停止。
4）把内部缓冲里的字符逐个拷贝到目标 buf，直到满足 n 或内部缓冲再次为空。
复杂度分析
时间复杂度：单次调用 O(n)（按实际搬运字符计）。
空间复杂度：O(1)（固定 4 大小缓冲区）。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
/**
* The read4 API is defined in the parent class Reader4.
* int read4(char[] buf4);
*/
public class Solution extends Reader4 {
private final char[] buf4 = new char[4];
private int ptr = 0;
private int cnt = 0;
public int read(char[] buf, int n) {
int i = 0;
while (i < n) {
if (ptr == cnt) {
cnt = read4(buf4);
ptr = 0;
if (cnt == 0) break;
}
while (i < n && ptr < cnt) {
buf[i++] = buf4[ptr++];
}
}
return i;
}
}// read4 is provided by the platform.
// func read4(buf4 []byte) int
type Solution struct {
buf4 [4]byte
ptr int
cnt int
}
func Constructor() Solution {
return Solution{}
}
func (s *Solution) Read(buf []byte, n int) int {
i := 0
for i < n {
if s.ptr == s.cnt {
s.cnt = read4(s.buf4[:])
s.ptr = 0
if s.cnt == 0 {
break
}
}
for i < n && s.ptr < s.cnt {
buf[i] = s.buf4[s.ptr]
i++
s.ptr++
}
}
return i
}// The read4 API is defined in the parent class Reader4.
// int read4(char *buf4);
class Solution : public Reader4 {
private:
char buf4_[4];
int ptr_ = 0;
int cnt_ = 0;
public:
int read(char *buf, int n) {
int i = 0;
while (i < n) {
if (ptr_ == cnt_) {
cnt_ = read4(buf4_);
ptr_ = 0;
if (cnt_ == 0) break;
}
while (i < n && ptr_ < cnt_) {
buf[i++] = buf4_[ptr_++];
}
}
return i;
}
};# The read4 API is already defined for you.
# def read4(buf4: List[str]) -> int:
class Solution:
def __init__(self):
self.buf4 = [''] * 4
self.ptr = 0
self.cnt = 0
def read(self, buf: List[str], n: int) -> int:
i = 0
while i < n:
if self.ptr == self.cnt:
self.cnt = read4(self.buf4)
self.ptr = 0
if self.cnt == 0:
break
while i < n and self.ptr < self.cnt:
buf[i] = self.buf4[self.ptr]
i += 1
self.ptr += 1
return i/**
* @param {function} read4
* @return {function}
*/
var solution = function(read4) {
const cache = new Array(4);
let ptr = 0;
let cnt = 0;
/**
* @param {character[]} buf
* @param {number} n
* @return {number}
*/
return function(buf, n) {
let i = 0;
while (i < n) {
if (ptr === cnt) {
cnt = read4(cache);
ptr = 0;
if (cnt === 0) break;
}
while (i < n && ptr < cnt) {
buf[i++] = cache[ptr++];
}
}
return i;
};
};
Comments