blob: c7692e7f3bb83a93a8906dc4898a388676d57a2a (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
# 900. RLE Iterator
"""
we can use run length encoding to encode a sequence of integers. in a run
length encoded array of even length encoding, for all even 'i', 'encoding[i]'
tells us the number of times that the non negative integer value 'encoding[i
+ 1]' is repeated in the sequence. given that a run length encoded array,
design an iterator that iterates through it.
"""
class RLEIterator(object):
def __init__(self, encoding):
"""
:type encoding: List[int]
"""
self.vals = encoding
self.i = 0
def next(self, n):
"""
:type n: int
:rtype: int
"""
while n > 0 and self.i < len(self.vals):
if n > self.vals[self.i]:
n -= self.vals[self.i]
self.i += 2
else:
self.vals[self.i] -= n
return self.vals[self.i + 1]
return -1
if __name__ == "__main__":
obj = RLEIterator([3, 8, 0, 9, 2, 5])
print(obj.next(2))
print(obj.next(1))
print(obj.next(1))
print(obj.next(2))
|