Giả sử có hai mảng 1D, chúng ta phải triển khai một trình lặp sẽ trả về luân phiên các phần tử của chúng. Sẽ có hai phương pháp -
-
next () - để lấy phần tử tiếp theo
-
hasNext () - để kiểm tra xem phần tử tiếp theo có hiện diện hay không.
Vì vậy, nếu đầu vào là v1 =[1,2] v2 =[3,4,5,6], thì đầu ra sẽ là [1,3,2,4,5,6],
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định một hàng đợi q trong số các cặp
-
Từ bộ khởi tạo, hai mảng v1 và v2,
-
nếu kích thước của v1, thì -
-
chèn {0, 0} vào q
-
-
nếu kích thước của v2, thì -
-
chèn {0, 1} vào q
-
-
Xác định nhiệt độ một cặp
-
temp:=phần tử đầu tiên của q
-
xóa phần tử khỏi q
-
ret:=0
-
nếu temp.second giống với 1, thì -
-
ret:=v2 [temp.first]
-
(tăng temp. đầu tiên lên 1)
-
nếu temp.first
-
chèn tạm thời vào q
-
-
-
Nếu không
-
ret:=v1 [temp.first]
-
(tăng temp. đầu tiên lên 1)
-
if temp.first
-
chèn tạm thời vào q
-
-
-
trả lại ret
-
Xác định một hàm hasNext ()
-
trả về true khi q không rỗng
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#include <bits/stdc++.h>
using namespace std;
class ZigzagIterator {
public:
queue <pair<int, int>> q;
vector <int< v1, v2;
ZigzagIterator(vector<int<& v1, vector<int<& v2) {
this->v1 = v1;
this->v2 = v2;
if (v1.size()) {
q.push({ 0, 0 });
}
if (v2.size()) {
q.push({ 0, 1 });
}
}
int next() {
pair<int, int> temp;
temp = q.front();
q.pop();
int ret = 0;
if (temp.second == 1) {
ret = v2[temp.first];
temp.first++;
if (temp.first < v2.size())
q.push(temp);
}
else {
ret = v1[temp.first];
temp.first++;
if (temp.first < v1.size())
q.push(temp);
}
return ret;
}
bool hasNext() {
return !q.empty();
}
};
main(){
vector<int< v1 = {1,3,5,7}, v2 = {2,4,6,8,10,12,17};
ZigzagIterator ob(v1, v2);
cout << (ob.next()) << endl;
cout << (ob.next()) << endl;
cout << (ob.hasNext() ? "True" : "False") << endl;
cout << (ob.next()) << endl;
cout << (ob.next()) << endl;
cout << (ob.next()) << endl;
cout << (ob.hasNext() ? "True" : "False") << endl;
cout << (ob.next()) << endl;
cout << (ob.next()) << endl;
cout << (ob.next()) << endl;
cout << (ob.next()) << endl;
cout << (ob.hasNext() ? "True" : "False") << endl;
cout << (ob.next()) << endl;
cout << (ob.next()) << endl;
cout << (ob.hasNext() ? "True" : "False") << endl;
} Đầu vào
{1,3,5,7},{2,4,6,8,10,12,17} Đầu ra
1 2 True 3 4 5 True 6 7 8 10 True 12 17 False