C++ without paying too much attention on direction switch


  • 13
    H

    Put all diagonal sequences from top-right to bottom-left to an array and then combine all sequence together by reversing odd sequences.

    class Solution {
    public:
        vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
            int m = matrix.size();
            if (m == 0) return vector<int>();
            int n = matrix[0].size();
            vector<vector<int>> tmp (m+n-1);
            for (int i = 0; i < m+n-1 ; i++) {
                int row = max(0, i-n+1);
                int col = min(i, n-1);
                for (; col >= 0 && row < m; row++, col--) {
                    tmp[i].push_back(matrix[row][col]);
                }
            }
            vector<int> res;
            for (int i = 0; i< tmp.size(); i++) {
                if (i % 2) res.insert(res.end(), tmp[i].begin(), tmp[i].end());
                else res.insert(res.end(), tmp[i].rbegin(), tmp[i].rend());
            }
            return res;
        }
    };
    

  • 4
    Y

    Some simple modification eliminates the use of a temporary storage.

    vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
        
        if (matrix.size() == 0 || matrix[0].size() == 0) return {};
        int m = matrix.size(), n = matrix[0].size();
        
        vector<int> res;
        for (int i = 0; i < m+n-1; i++) {
            int begin_pos = res.size();
            for (int row = max(0, i-n+1), col = min(i, n-1); col >= 0 && row < m; row++, col--)
                res.push_back(matrix[row][col]);
            if (i % 2 == 0) reverse(res.begin() + begin_pos, res.end());
        }
        
        return res;
    }
    

  • 0
    S

    clean clean!


  • 0
    S

    @yuanqili nicuuue


Log in to reply
 

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