900.RLE Iterator
900.RLE iterator
题目难度 Medium
编写一个遍历游程编码序列的迭代器。 迭代器由 RLEIterator(int[] A) 初始化,其中 A 是某个序列的游程编码。更具体地,对于所有偶数 i,A[i] 告诉我们在序列中重复非负整数值 A[i + 1] 的次数。 迭代器支持一个函数:next(int n),它耗尽接下来的 n 个元素(n >= 1)并返回以这种方式耗去的最后一个元素。如果没有剩余的元素可供耗尽,则 next 返回 -1 。 例如,我们以 A = [3,8,0,9,2,5] 开始,这是序列 [8,8,8,5,5] 的游程编码。这是因为该序列可以读作 “三个八,零个九,两个五”。
1
示例:
2
3
输入:["RLEIterator","next","next","next","next"], [[[3,8,0,9,2,5]],[2],[1],[1],[2]]
4
输出:[null,8,8,5,-1]
5
解释:
6
RLEIterator 由 RLEIterator([3,8,0,9,2,5]) 初始化。
7
这映射到序列 [8,8,8,5,5]。
8
然后调用 RLEIterator.next 4次。
9
10
.next(2) 耗去序列的 2 个项,返回 8。现在剩下的序列是 [8, 5, 5]。
11
12
.next(1) 耗去序列的 1 个项,返回 8。现在剩下的序列是 [5, 5]。
13
14
.next(1) 耗去序列的 1 个项,返回 5。现在剩下的序列是 [5]。
15
16
.next(2) 耗去序列的 2 个项,返回 -1。 这是由于第一个被耗去的项是 5,
17
但第二个项并不存在。由于最后一个要耗去的项不存在,我们返回 -1。
18
19
20
提示:
21
22
0 <= A.length <= 1000
23
A.length 是偶数。
24
0 <= A[i] <= 10^9
25
每个测试用例最多调用 1000 次 RLEIterator.next(int n)。
26
每次调用 RLEIterator.next(int n) 都有 1 <= n <= 10^9 。
Copied!
方法: 方法比较简单,判断n是否大于A[0],如果是,则n-=A[0],然后A向量删掉前两个元素,继续循环判断,最后返回n删除的元素。
1
class RLEIterator {
2
private:
3
vector<int >a;
4
public:
5
RLEIterator(vector<int> A) {
6
a=A;
7
}
8
9
int next(int n) {
10
int result;
11
12
while(n>0)
13
{
14
if(a.size()==0)
15
{
16
return -1;
17
}
18
19
if(n >=a[0] )
20
{
21
n -=a[0];
22
result = a[1];
23
a.erase(a.begin());
24
a.erase(a.begin());
25
26
}
27
else
28
{
29
a[0] -= n;
30
n=0;
31
result =a[1];
32
}
33
34
}
35
36
return result;
37
}
38
};
39
40
/**
41
* Your RLEIterator object will be instantiated and called as such:
42
* RLEIterator obj = new RLEIterator(A);
43
* int param_1 = obj.next(n);
44
*/
Copied!
Copy link