Giả sử chúng ta phải tạo một trình lặp lặp qua một trình tự được mã hóa theo độ dài lần chạy. Ở đây trình lặp được khởi tạo bằng cách gọi RLEIterator (int [] A), trong đó A là mã hóa độ dài chạy của một chuỗi. Vì vậy, chúng ta có thể nói rằng với tất cả các i chẵn, A [i] cho chúng ta biết số lần giá trị nguyên không âm A [i + 1] được lặp lại trong dãy. Ở đây trình vòng lặp hỗ trợ một chức năng -
-
next (int n):Hàm này sử dụng hết n phần tử tiếp theo (n> =1) và trả về phần tử cuối cùng đã hết theo cách này. Vì vậy, nếu không còn phần tử nào để cạn kiệt, thay vào đó, tiếp theo sẽ trả về -1.
Giả sử chúng ta bắt đầu với A =[3,8,0,9,2,5], là một mã hóa độ dài chạy của chuỗi [8,8,8,5,5]. Điều này được thực hiện vì chuỗi có thể được đọc là "ba tám, không chín, hai fives". Vì vậy, sau khi khởi tạo chúng bằng A, nếu chúng ta gọi next (2), next (1), next (1), next (2), thì kết quả cuối cùng sẽ là [8, 8, 5, -1].
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Trong trình khởi tạo, khởi tạo mảng là A và đặt chỉ mục:=0
-
Trong phương thức next (), nó lấy n làm đầu vào. điều này sẽ hoạt động như sau
-
trong khi chỉ mục
A [chỉ số] -
n:=n - A [chỉ số] và tăng chỉ số lên 2
-
-
nếu chỉ mục> kích thước của mảng A, thì trả về -1
-
A [index]:=A [index] - n
-
trả về A [chỉ mục + 1]
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#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;
} Đầu vào
Initialize with [3,8,0,9,2,5] and call next(2), next(1), next(1), next(2)
Đầu ra
8 8 5 -1