RLE Iterator trong C++

Tạo iterator cho chuỗi run-length encoded. Khởi tạo RLEIterator(A): A[i] (i chẵn) là số lần lặp của A[i+1]. Hàm next(n): tiêu thụ n phần tử, trả về phần tử cuối tiêu thụ, hoặc -1 nếu hết.

Ví dụ: A=[3,8,0,9,2,5] mã hóa [8,8,8,5,5]. next(2)→8, next(1)→8, next(1)→5, next(2)→-1.

Giải pháp:

• Lưu A, idx=0

• next(n): while idxA[idx]: n-=A[idx], idx+=2

• Nếu idx≥A.size: return -1

• A[idx]-=n, return A[idx+1]

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] -= n; return A[idx + 1];    } }; int main(){ vector<int> v = {3,8,0,9,2,5}; RLEIterator ob(v); cout << ob.next(2) << endl << ob.next(1) << endl << ob.next(1) << endl << ob.next(2) << endl; }

Đầu vào

Khởi tạo [3,8,0,9,2,5] gọi next(2), next(1), next(1), next(2)

Đầu ra

8 8 5 -1