900. RLE 迭代器
我们可以使用游程编码(即 RLE )来编码一个整数序列。在偶数长度 encoding ( 从 0 开始 )的游程编码数组中，对于所有偶数 i ，encoding[i] 告诉我们非负整数 encoding[i + 1] 在序列中重复的次数。
arr = [8,8,8,5,5] 可以被编码为 encoding =[3,8,2,5] 。encoding =[3,8,0,9,2,5] 和 encoding =[2,8,1,8,2,5] 也是 arr 有效的 RLE 。给定一个游程长度的编码数组，设计一个迭代器来遍历它。
实现 RLEIterator 类:
RLEIterator(int[] encoded) 用编码后的数组初始化对象。int next(int n) 以这种方式耗尽后 n 个元素并返回最后一个耗尽的元素。如果没有剩余的元素要耗尽，则返回 -1 。
示例 1：
输入： ["RLEIterator","next","next","next","next"] [[[3,8,0,9,2,5]],[2],[1],[1],[2]] 输出： [null,8,8,5,-1] 解释： RLEIterator rLEIterator = new RLEIterator([3, 8, 0, 9, 2, 5]); // 这映射到序列 [8,8,8,5,5]。 rLEIterator.next(2); // 耗去序列的 2 个项，返回 8。现在剩下的序列是 [8, 5, 5]。 rLEIterator.next(1); // 耗去序列的 1 个项，返回 8。现在剩下的序列是 [5, 5]。 rLEIterator.next(1); // 耗去序列的 1 个项，返回 5。现在剩下的序列是 [5]。 rLEIterator.next(2); // 耗去序列的 2 个项，返回 -1。 这是由于第一个被耗去的项是 5， 但第二个项并不存在。由于最后一个要耗去的项不存在，我们返回 -1。
提示：
2 <= encoding.length <= 1000encoding.length 为偶0 <= encoding[i] <= 1091 <= n <= 109next 不高于 1000 次 原站题解
golang 解法, 执行用时: 4 ms, 内存消耗: 3.5 MB, 提交时间: 2023-05-31 15:33:51
type RLEIterator struct {
data []int
pos int
left int
}
func Constructor(encoding []int) RLEIterator {
return RLEIterator{encoding, -2, 0}
}
func (this *RLEIterator) Next(n int) int {
for n > this.left {
this.pos += 2
if this.pos >= len(this.data) {
return -1
}
this.left += this.data[this.pos]
}
if this.pos >= len(this.data) {
return -1
}
this.left -= n
// fmt.Println(n,this.data[this.pos+1])
return this.data[this.pos+1]
}
/**
* Your RLEIterator object will be instantiated and called as such:
* obj := Constructor(A);
* param_1 := obj.Next(n);
*/
golang 解法, 执行用时: 8 ms, 内存消耗: 3.5 MB, 提交时间: 2023-05-31 15:33:28
type RLEIterator struct {
list []int
cur int
}
func Constructor(A []int) RLEIterator {
return RLEIterator{
list:A,
cur:0,
}
}
// 1815
func (this *RLEIterator) Next(n int) int {
for i:=0;i<len(this.list)-1;i+=2{
if i%2==0&&this.list[i]!=0{
if n<=this.list[i]{
this.list[i]-=n
return this.list[i+1]
}else{
n-=this.list[i]
this.list[i] = 0
this.cur = i+2
}
}
}
return -1
}
/**
* Your RLEIterator object will be instantiated and called as such:
* obj := Constructor(A);
* param_1 := obj.Next(n);
*/
golang 解法, 执行用时: 4 ms, 内存消耗: 3.5 MB, 提交时间: 2023-05-31 15:33:13
type RLEIterator struct {
oriElement []int // 初始化的数组
curElementIndex int // 当前元素数量的位置
haveDeletedTimes int // 当前元素已经删过的次数
}
func Constructor(A []int) RLEIterator {
return RLEIterator{oriElement:A, curElementIndex:0, haveDeletedTimes:0}
}
func (this *RLEIterator) Next(n int) int {
for this.curElementIndex < len(this.oriElement) {
remain:= this.oriElement[this.curElementIndex] - this.haveDeletedTimes
if remain >= n {
this.haveDeletedTimes += n
return this.oriElement[this.curElementIndex + 1]
}
n -= remain
this.haveDeletedTimes = 0
this.curElementIndex += 2
}
return -1
}
/**
* Your RLEIterator object will be instantiated and called as such:
* obj := Constructor(encoding);
* param_1 := obj.Next(n);
*/
python3 解法, 执行用时: 48 ms, 内存消耗: 16.5 MB, 提交时间: 2023-05-31 15:32:16
class RLEIterator:
def __init__(self, encoding: List[int]):
self.A = encoding
self.i = 0
self.q = 0
def next(self, n: int) -> int:
while self.i < len(self.A):
if self.q + n > self.A[self.i]:
n -= self.A[self.i] - self.q
self.q = 0
self.i += 2
else:
self.q += n
return self.A[self.i+1]
return -1
# Your RLEIterator object will be instantiated and called as such:
# obj = RLEIterator(encoding)
# param_1 = obj.next(n)
java 解法, 执行用时: 4 ms, 内存消耗: 40.6 MB, 提交时间: 2023-05-31 15:31:19
class RLEIterator {
int[] A;
int i, q;
public RLEIterator(int[] A) {
this.A = A;
i = q = 0;
}
public int next(int n) {
while (i < A.length) {
if (q + n > A[i]) {
n -= A[i] - q;
q = 0;
i += 2;
} else {
q += n;
return A[i+1];
}
}
return -1;
}
}
/**
* Your RLEIterator object will be instantiated and called as such:
* RLEIterator obj = new RLEIterator(encoding);
* int param_1 = obj.next(n);
*/