Flatten 2D Vector ใน C++

สมมติว่ามี 2D vector เราต้องออกแบบและ implement iterator เพื่อ flatten 2d vector นั้น จะมีเมธอดต่างๆ ดังนี้ −

• next() − จะคืนค่าสมาชิกถัดไปของสมาชิกปัจจุบัน

• hasNext() − จะตรวจสอบว่ามีสมาชิกถัดไปหรือไม่

เช่น ถ้าอินพุทเป็น [[1,2],[3],[4]] แล้วถ้าเราเรียกฟังก์ชันดังนี้ −

• iterator.next();

• iterator.next();

• iterator.next();

• iterator.hasNext();

• iterator.hasNext();

• iterator.next();

• iterator.hasNext();

ผลลัพธ์จะเป็น [1,2,3,true, true,4,false]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนดังนี้ −

• กำหนดอาร์เรย์ 2 มิติ v

• กำหนด initializer รับอาร์เรย์ 2 มิติ v

• rowPointer := 0

• colPointer := 0

• n := ขนาดของ v

• ลูป while (rowPointer < n และ colPointer >= ขนาดของ v[rowPointer]) ทำ −

  • เพิ่ม rowPointer ขึ้น 1

• กำหนดฟังก์ชัน next()

• x := v[rowPointer][colPointer]

• เพิ่ม colPointer ขึ้น 1

• ถ้า colPointer เท่ากับขนาดของ v[rowPointer] แล้ว −

  • colPointer := 0

  • เพิ่ม rowPointer ขึ้น 1

  • ลูป while (rowPointer < n และ colPointer >= ขนาดของ v[rowPointer]) ทำ −

    • เพิ่ม rowPointer ขึ้น 1

• คืนค่า x

• กำหนดฟังก์ชัน hasNext()

• คืนค่า false เมื่อ rowPointer เท่ากับ n

ตัวอย่าง

ลองดูการติดตั้งต่อไปนี้เพื่อให้เข้าใจได้ดีขึ้น −

#include <bits/stdc++.h> using namespace std; class Vector2D { public:    int rowPointer, colPointer;    int n;    vector<vector<int> > v;    Vector2D(vector<vector<int> >& v){       this->v = v;       rowPointer = 0;       colPointer = 0;       n = v.size();       while (rowPointer < n && colPointer >= v[rowPointer].size()){          rowPointer++;       }    }    int next(){       //cout << rowPointer << " " << colPointer << endl;       int x = v[rowPointer][colPointer];       colPointer++;       if (colPointer == v[rowPointer].size()) {          colPointer = 0;          rowPointer++;          while (rowPointer < n && colPointer >= v[rowPointer].size()) {             rowPointer++;          }       }       return x;    }    bool hasNext(){       return !(rowPointer == n);    } }; main(){    vector<vector<int>> v = {{1,2},{3},{4}};    Vector2D ob(v);    cout << (ob.next()) << endl;    cout << (ob.next()) << endl;    cout << (ob.next()) << endl;    cout << (ob.hasNext()) << endl;    cout << (ob.next()) << endl;    cout << (ob.hasNext()); }

อินพุท

ob.next() ob.next() ob.next() ob.hasNext() ob.next() ob.hasNext()

เอาต์พุท

1 2 3 1 4 0