数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++中的RLE迭代器
假设我们必须创建一个迭代器，用于迭代运行长度编码序列。在这里，迭代器通过调用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]的运行长度编码。这是因为该序列可以解读为“三个8，零个9，两个5”。因此，在用A初始化它们之后，如果我们调用next(2), next(1), next(1), next(2)，那么最终结果将是[8, 8, 5, -1]。
为了解决这个问题，我们将遵循以下步骤：
在初始化器中，将数组初始化为A，并将index := 0
在next()方法中，它接收n作为输入。它将按如下方式工作：
当index < A的大小 且 n > A[index]
n := n – A[index]，并将index增加2
如果index > 数组A的大小，则返回-1
A[index] := A[index] – n
返回A[index + 1]
让我们看一下下面的实现以更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class RLEIterator {
public:
vector <int> A;
int idx = 0;
RLEIterator(vector<int>& A) {
this->A = A;
idx = 0;
}
int next(int n) {
while(idx < A.size() && n > A[idx]){
n -= A[idx];
idx += 2;
}
if(idx >= A.size()) return -1;
A[idx] = A[idx] - n;
return A[idx + 1];
}
};
main(){
vector<int> v = {3,8,0,9,2,5};
RLEIterator ob(v);
cout << (ob.next(2)) << endl;
cout << (ob.next(1)) << endl;
cout << (ob.next(1)) << endl;
cout << (ob.next(2)) << endl;
}输入
Initialize with [3,8,0,9,2,5] and call next(2), next(1), next(1), next(2)
输出
8 8 5 -1
更新于：2020年4月30日
237 次浏览
广告