資料結構
網路
關係資料庫管理系統(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 次瀏覽
廣告