C++ ZigZag Problem Set Summary


  • 0
    F

    Problem 6 ---- The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

    class Solution {
    public:
        string convert(string s, int numRows) {
            if (numRows <= 1)
                return s;
            
            const int len = (int)s.size();
            string str[numRows];
            int row = 0, step = 1;
            //by flipping the step between 1 and -1, we can write all the str to its correct row position
            for (int i = 0; i < len; i++) {
                str[row].push_back(s[i]);
                if (row == 0)
                    step = 1;
                else if (row == numRows - 1)
                    step = -1;
                row += step;
            }
            s.clear();
            for (int j = 0; j < numRows; j++)  s.append(str[j]);
            return s;
        }
    };
    

    Problem 103 Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

    class Solution {
    public:
        vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
            vector<vector<int>> result;
            if(!root) return result;
            deque<TreeNode*> dq;
            dq.push_back(root);
            int flag = 0;
            while (!dq.empty()) {
                /** use the count to record the level element count **/
                int count = dq.size();
                vector<int> level;
                while (count-- > 0) {
                    TreeNode* cur = dq.front();
                    dq.pop_front();
                    level.push_back(cur->val);
                    if (cur->left)  dq.push_back(cur->left);
                    if (cur->right) dq.push_back(cur->right);
                }
                if (flag & 1)  reverse(level.begin(), level.end());
                result.push_back(level);
                flag ++;
            }
            return result;
        }
    };
    

    ZigZag Iterator Problem Given two 1d vectors, implement an iterator to return their elements alternately. For example, given two 1d vectors: v1 = [1, 2] v2 = [3, 4, 5, 6] By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1, 3, 2, 4, 5, 6].

    class ZigzagIterator {
    public:
        ZigzagIterator(vector<int>& v1, vector<int>& v2) {
            v.push_back(v1);
            v.push_back(v2);
            i = j = 0;
        }
        int next() {
            return i <= j ? v[0][i++] : v[1][j++];
        }
        bool hasNext() {
            if (i >= v[0].size()) i = INT_MAX;
            if (j >= v[1].size()) j = INT_MAX;
            return i < v[0].size() || j < v[1].size();
        }
    private:
        vector<vector<int>> v;
        int i, j;
    };
    

    Follow up , what should we do if we want to do zigzag iterator for K arrays :

    class ZigzagIterator {
    public:
        ZigzagIterator(vector<int>& v1, vector<int>& v2) {
            if (!v1.empty()) q.push(make_pair(v1.begin(), v1.end()));
            if (!v2.empty()) q.push(make_pair(v2.begin(), v2.end()));
        }
        int next() {
            auto it = q.front().first, end = q.front().second;
            q.pop();
            if (it + 1 != end) q.push(make_pair(it + 1, end));
            return *it;
        }
        bool hasNext() {
            return !q.empty();
        }
    private:
        queue<pair<vector<int>::iterator, vector<int>::iterator>> q;
    };
    

    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].

    Brute Force Solution

    class Vector2D {
    public:
        Vector2D(vector<vector<int>>& vec2d) {
            for (auto a : vec2d) {
                v.insert(v.end(), a.begin(), a.end());
            }    
        }
        int next() {
            return v[i++];
        }
        bool hasNext() {
            return i < v.size();
        }
    private:
        vector<int> v;
        int i = 0;
    };
    
    

    We can keep 2 variable x and y , we check whether x is valid and y is valid, and we can change to the new line once we meet the ending of the line

    class Vector2D {
    public:
        Vector2D(vector<vector<int>>& vec2d) {
            v = vec2d;
            x = y = 0;
        }
        int next() {
            return v[x][y++];
        }
        bool hasNext() {
            while (x < v.size() && y == v[x].size()) {
                ++x; 
                y = 0;
            }
            return x < v.size();
        }    
    private:
        vector<vector<int>> v;
        int x, y;
    };
    
    

    Follow Up : implement it with iterator style

    class Vector2D {
    public:
        Vector2D(vector<vector<int>>& vec2d) {
            x = vec2d.begin();
            end = vec2d.end();
        }
        int next() {
            return (*x)[y++];
        }
        bool hasNext() {
            while (x != end && y == (*x).size()) {
                ++x; 
                y = 0;
            }
            return x != end;
        }
    private:
        vector<vector<int>>::iterator x, end;
        int y = 0;
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.