281.Zigzag Iterator

Given two 1d vectors, implement an iterator to return their elements alternately.

Example

Given two 1d vectors:

v1 = [1, 2]
v2 = [3, 4, 5, 6]

By calling next repeatedly until hasNext returnsfalse, the order of elements returned by next should be:[1, 3, 2, 4, 5, 6].

S: iterator

class ZigzagIterator {
public:
    ZigzagIterator(vector<int>& v1, vector<int>& v2) {
        begin.resize(2);
        end.resize(2);
        begin[0] = v1.begin();
        begin[1] = v2.begin();
        end[0] = v1.end();
        end[1] = v2.end();
        flag = 0;
    }

    int next() {
        if (!hasNext()) return -1;
        int result;
        if (begin[0] == end[0]) {
            result = *begin[1];
            begin[1]++;
        } else if (begin[1] == end[1]) {
            result = *begin[0];
            begin[0]++;
        } else {
            result = *begin[flag];
            begin[flag]++;
            flag = (flag + 1) % 2;
        }
        return result;
    }

    bool hasNext() {
        return begin[0] != end[0] || begin[1] != end[1];
    }

private:
    vector<vector<int>::iterator> begin;
    vector<vector<int>::iterator> end;
    int flag;
};

Zigzag Iterator II

Follow up Zigzag Iterator: What if you are given k 1d vectors? How well can your code be extended to such cases? The "Zigzag" order is not clearly defined and is ambiguous for k > 2 cases. If "Zigzag" does not look right to you, replace "Zigzag" with "Cyclic".

Example

Givenk = 31d vectors:

[1,2,3]
[4,5,6,7]
[8,9]

Return[1,4,8,2,5,9,3,6,7].

S: queue

//注意： 未通过编译
class ZigzagIterator2 {
public:
    ZigzagIterator2(vector<vector<int>>& vecs) {
        for (vector<int> v : vecs) {
            if (v.size()) q.push(make_pair(v.begin(), v.end());
        }
    }

    int next() {
        int result = *(q.front().first);
        q.front().first++;
        if (q.front().first != q.front().second) q.push(q.front());
        q.pop();
        return result;
    }

    bool hasNext() {
        return !q.empty();      
    }

private:
    queue<pair<vector<int>::iterator, vector<int>::iterator>> q;
};

251. Flatten 2D Vector

Implement an iterator to flatten a 2d vector.

For example,
Given 2d vector =

[
  [1,2],
  [3],
  [4,5,6]
]

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be:[1,2,3,4,5,6].

S: iterator

存储二维数组开始和结尾的iterator，以及当前行的index。注意对某一行为空数组的情况的处理

class Vector2D {
public:
    Vector2D(vector<vector<int>>& vec2d) {
        startIt = vec2d.begin();
        endIt = vec2d.end();
        idx = 0;
    }

    int next() {
        int val = (*startIt)[idx++];
        return val;
    }

    bool hasNext() {
       while (startIt != endIt && idx == (*startIt).size()) { //当有空数组的情况
           startIt++;
           idx = 0;
       }
       return startIt != endIt;
    }
private:
    vector<vector<int>>::iterator startIt, endIt;
    int idx;
};