RLE Iterator ใน C++

คำอธิบายปัญหา

สร้าง iterator สำหรับ run-length encoded sequence A โดย A[even] = จำนวนครั้ง, A[odd] = ค่า ฟังก์ชัน next(n): ข้าม n ตัว คืนค่าตัวสุดท้ายที่ข้าม ถ้าไม่พอคืน -1

ตัวอย่าง: A=[3,8,0,9,2,5] แทน [8,8,8,5,5], next(2)=8, next(1)=8, next(1)=5, next(2)=-1

วิธีแก้ปัญหา

1. เก็บ index ปัจจุบัน (ชี้ที่ count)
2. next(n): ลบ n ออกจาก count ปัจจุบัน จน n=0 หรือหมดอาร์เรย์
3. ถ้าหมดคืน -1, มิฉะนั้นคืนค่าที่ index+1

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class RLEIterator {
public:
    vector<int> A;
    int idx = 0;
    
    RLEIterator(vector<int>& A) : 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; // 8
    cout << ob.next(1) << endl; // 8
    cout << ob.next(1) << endl; // 5
    cout << ob.next(2) << endl; // -1
    return 0;
}

อินพุต

Initialize with [3,8,0,9,2,5] and call next(2), next(1), next(1), next(2)

เอาต์พุต

8 8 5 -1