Problem
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 <= 1000A.lengthis an even integer.0 <= A[i] <= 10^9- There are at most
1000calls toRLEIterator.next(int n)per test case. - Each call to
RLEIterator.next(int n)will have1 <= n <= 10^9.
Solution: Simulation
Time complexity: O(|A|)
Space complexity: O(|A|)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Author: Huahua, 4 ms class RLEIterator { public: RLEIterator(vector<int> A): A_(std::move(A)), i_(0) {} int next(int n) { while (n && i_ < A_.size()) { if (n >= A_[i_]) { n -= A_[i_]; i_ += 2; if (n == 0) return A_[i_ - 1]; } else { A_[i_] -= n; return A_[i_ + 1]; } } return -1; } private: int i_; vector<int> A_; }; |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Author: Huahua, 73 ms class RLEIterator { private int[] A; private int i; public RLEIterator(int[] A) { this.A = A; this.i = 0; } public int next(int n) { while (n >= 0 && i < A.length) { if (n >= A[i]) { n -= A[i]; i += 2; if (n == 0) return A[i - 1]; } else { A[i] -= n; return A[i + 1]; } } return -1; } } |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
# Author: Huahua, 44 ms class RLEIterator: def __init__(self, A): self.A = A self.i = 0 def next(self, n): while n != 0 and self.i < len(self.A): if n >= self.A[self.i]: n -= self.A[self.i] self.i += 2 if n == 0: return self.A[self.i - 1] else: self.A[self.i] -= n return self.A[self.i + 1] return -1 |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment