Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/900.html
900. RLE Iterator (Medium)
Write an iterator that iterates through a run-length encoded sequence.
The iterator is initialized by RLEIterator(int[] A)
, where A
is a run-length encoding of some sequence. More specifically, for all even i
, A[i]
tells us the number of times that the non-negative integer value A[i+1]
is repeated in the sequence.
The iterator supports one function: next(int n)
, which exhausts the next n
elements (n >= 1
) and returns the last element exhausted in this way. If there is no element left to exhaust, next
returns -1
instead.
For example, we start with A = [3,8,0,9,2,5]
, which is a run-length encoding of the sequence [8,8,8,5,5]
. This is because the sequence can be read as "three eights, zero nines, two fives".
Example 1:
Input: ["RLEIterator","next","next","next","next"], [[[3,8,0,9,2,5]],[2],[1],[1],[2]] Output: [null,8,8,5,-1] Explanation: RLEIterator is initialized with RLEIterator([3,8,0,9,2,5]). This maps to the sequence [8,8,8,5,5]. RLEIterator.next is then called 4 times: .next(2) exhausts 2 terms of the sequence, returning 8. The remaining sequence is now [8, 5, 5]. .next(1) exhausts 1 term of the sequence, returning 8. The remaining sequence is now [5, 5]. .next(1) exhausts 1 term of the sequence, returning 5. The remaining sequence is now [5]. .next(2) exhausts 2 terms, returning -1. This is because the first term exhausted was 5, but the second term did not exist. Since the last term exhausted does not exist, we return -1.
Note:
0 <= A.length <= 1000
A.length
is an even integer.0 <= A[i] <= 10^9
- There are at most
1000
calls toRLEIterator.next(int n)
per test case. - Each call to
RLEIterator.next(int n)
will have1 <= n <= 10^9
.
Related Topics:
Array
Solution 1.
-
class RLEIterator { private int[] encoding; private int curr; private int i; public RLEIterator(int[] encoding) { this.encoding = encoding; curr = 0; i = 0; } public int next(int n) { while (i < encoding.length) { if (curr + n > encoding[i]) { n -= encoding[i] - curr; i += 2; curr = 0; } else { curr += n; return encoding[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); */
-
class RLEIterator { public: vector<int> encoding; int curr; int i; RLEIterator(vector<int>& encoding) { this->encoding = encoding; this->curr = 0; this->i = 0; } int next(int n) { while (i < encoding.size()) { if (curr + n > encoding[i]) { n -= encoding[i] - curr; curr = 0; i += 2; } else { curr += n; return encoding[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); */
-
class RLEIterator: def __init__(self, encoding: List[int]): self.encoding = encoding self.i = 0 self.curr = 0 def next(self, n: int) -> int: while self.i < len(self.encoding): if self.curr + n > self.encoding[self.i]: n -= self.encoding[self.i] - self.curr self.curr = 0 self.i += 2 else: self.curr += n return self.encoding[self.i + 1] return -1 # Your RLEIterator object will be instantiated and called as such: # obj = RLEIterator(encoding) # param_1 = obj.next(n)
-
type RLEIterator struct { encoding []int curr int i int } func Constructor(encoding []int) RLEIterator { return RLEIterator{encoding: encoding, curr: 0, i: 0} } func (this *RLEIterator) Next(n int) int { for this.i < len(this.encoding) { if this.curr+n > this.encoding[this.i] { n -= this.encoding[this.i] - this.curr this.curr = 0 this.i += 2 } else { this.curr += n return this.encoding[this.i+1] } } return -1 } /** * Your RLEIterator object will be instantiated and called as such: * obj := Constructor(encoding); * param_1 := obj.Next(n); */