[Swift]LeetCode900. RLE 迭代器 | RLE Iterator
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10607679.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
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 nelements (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: [[[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.
编写一个遍历游程编码序列的迭代器。
迭代器由 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] 的游程编码。这是因为该序列可以读作 “三个八，零个九，两个五”。
示例：
输入：["RLEIterator","next","next","next","next"], [[[3,8,0,9,2,5]],[2],[1],[1],[2]] 输出：[null,8,8,5,-1] 解释： RLEIterator 由 RLEIterator([3,8,0,9,2,5]) 初始化。 这映射到序列 [8,8,8,5,5]。 然后调用 RLEIterator.next 4次。 .next(2) 耗去序列的 2 个项，返回 8。现在剩下的序列是 [8, 5, 5]。 .next(1) 耗去序列的 1 个项，返回 8。现在剩下的序列是 [5, 5]。 .next(1) 耗去序列的 1 个项，返回 5。现在剩下的序列是 [5]。 .next(2) 耗去序列的 2 个项，返回 -1。 这是由于第一个被耗去的项是 5， 但第二个项并不存在。由于最后一个要耗去的项不存在，我们返回 -1。
提示：
0 <= A.length <= 1000A.length是偶数。0 <= A[i] <= 10^9- 每个测试用例最多调用
1000次RLEIterator.next(int n)。 - 每次调用
RLEIterator.next(int n)都有1 <= n <= 10^9。
Runtime: 24 ms
Memory Usage: 19.6 MB
1 class RLEIterator {
2 var index:Int
3 var A:[Int]
4
5 init(_ A: [Int]) {
6 self.A = A
7 index = 0
8 }
9
10 func next(_ n: Int) -> Int {
11 var n = n
12 while(index < A.count && n > A[index])
13 {
14 n -= A[index]
15 index += 2
16 }
17 if index >= A.count
18 {
19 return -1
20 }
21 A[index] -= n;
22 return A[index + 1]
23 }
24 }
25
26 /**
27 * Your RLEIterator object will be instantiated and called as such:
28 * let obj = RLEIterator(A)
29 * let ret_1: Int = obj.next(n)
30 */
31 24ms
1 class RLEIterator {
2 let array : [Int]
3 var currentPosition = 0
4 var currentCount = 0
5
6 init(_ A: [Int]) {
7 array = A
8 }
9
10 func next(_ n: Int) -> Int {
11 var n = n
12
13 while currentPosition < array.count {
14 if currentCount + n > array[currentPosition] {
15 n = n - (array[currentPosition] - currentCount)
16 currentCount = 0
17 currentPosition += 2
18 } else {
19 currentCount += n
20 return array[currentPosition + 1]
21 }
22 }
23 return -1
24 }
25 }32ms
1 class RLEIterator {
2
3 init(_ A: [Int]) {
4 var i = A.count - 2
5 while i >= 0 {
6 store.append(Record(A[i + 1], A[i]))
7 i -= 2
8 }
9 }
10
11 func next(_ n: Int) -> Int {
12 var n = n
13 while !store.isEmpty {
14 let k = min(store.last!.cnt, n)
15 store[store.count - 1].cnt -= k
16 n -= k
17 if n == 0 {
18 return store.last!.val
19 }
20 if store.last!.cnt == 0 {
21 store.removeLast()
22 }
23 }
24 return -1
25 }
26
27 struct Record {
28 var val: Int
29 var cnt: Int
30 init(_ val: Int, _ cnt: Int) {
31 self.val = val
32 self.cnt = cnt
33 }
34 }
35 var store = [Record]()
36 }40ms
1 class RLEIterator {
2 private let arr: [Int]
3 var cur = (0, 0)
4
5 init(_ A: [Int]) {
6 arr = A
7 cur = (0, A[0])
8 }
9
10 func next(_ n: Int) -> Int {
11 // diff = 2 | 1 | 1 | 2
12 var diff = n
13 // cur == (0, 3) | (0, 1) | (0,0) | (4,1)
14 // 3 - 2 < 0 => false, | 1 - 1 < 0 => false | 0-1 < 0 => true;0-1<0=>true;2-1<0=>false | 1 - 2 < 0 => true
15 while (cur.1 - diff) < 0 {
16 //||1;1| 1
17 diff -= cur.1
18 // || (2, 0);(4,0)|(6,1)
19 cur.0 += 2
20 if cur.0 >= arr.count {
21 return -1
22 }
23 // || (2, 0);(4,2)|(6)
24 cur.1 = arr[cur.0]
25 }
26 // (0,3) -> (0,1) | (0, 1) -> (0, 0) | (4,2) -> (4,1)
27 cur.1 -= diff
28 // false
29 if cur.0+1 >= arr.count {
30 return -1
31 }
32 // 8 | 8 | 5
33 return arr[cur.0+1]
34 }
35 }