สมมติว่าเราต้องสร้างตัววนซ้ำที่วนซ้ำผ่านลำดับการเข้ารหัสแบบรัน-ยาว ในที่นี้ ตัววนซ้ำจะเริ่มต้นโดยการเรียก RLEIterator(int[] A) โดยที่ A คือการเข้ารหัสความยาวรันของลำดับ ดังนั้นเราสามารถพูดได้ว่าสำหรับแม้แต่ i ทั้งหมด A[i] บอกเราถึงจำนวนครั้งที่ค่าจำนวนเต็มไม่เป็นลบ A[i+1] ซ้ำกันในลำดับ นี่ iterator รองรับหนึ่งฟังก์ชัน -
-
ถัดไป (int n):ฟังก์ชันนี้ทำให้องค์ประกอบ n ถัดไปหมด (n>=1) และส่งคืนองค์ประกอบสุดท้ายที่หมดด้วยวิธีนี้ ดังนั้นหากไม่มีองค์ประกอบเหลือที่จะระบายออก ครั้งต่อไปจะคืนค่า -1 แทน
สมมติว่าเราเริ่มต้นด้วย A =[3,8,0,9,2,5] ซึ่งเป็นการเข้ารหัสตามความยาวของลำดับ [8,8,8,5,5] สิ่งนี้ทำได้เนื่องจากลำดับสามารถอ่านได้ว่า "สามแปด ศูนย์เก้า สองห้า" ดังนั้น หลังจากที่เริ่มต้นด้วย A แล้ว หากเราเรียก next(2), next(1), next(1), next(2) ผลลัพธ์สุดท้ายจะเป็น [8, 8, 5, -1]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ใน initializer ให้เริ่มต้นอาร์เรย์เป็น A และตั้งค่าดัชนี :=0
-
ในเมธอด next() จะใช้ n เป็นอินพุต สิ่งนี้จะทำงานดังนี้
-
ขณะที่ดัชนี <ขนาดของ A และ n> A[ดัชนี]
-
n :=n – A[index] และเพิ่มดัชนีอีก 2
-
-
ถ้า index> ขนาดของอาร์เรย์ A ให้คืนค่า -1
-
A[index] :=A[index] – n
-
ส่งคืน A[ดัชนี + 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
