[LeetCode] 498. Diagonal Traverse

[grandyang]

 

Given a matrix of M x N elements (M rows, N columns), return all elements of the matrix in diagonal order as shown in the below image.

Example:

Input:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
Output:  [1,2,4,7,5,3,6,8,9]
Explanation:

 

Note:

1. The total number of elements of the given matrix will not exceed 10,000.

 

这道题给了我们一个mxn大小的数组，让我们进行对角线遍历，先向右上，然后左下，再右上，以此类推直至遍历完整个数组，题目中的例子和图示也能很好的帮我们理解。由于移动的方向不再是水平或竖直方向，而是对角线方向，那么每移动一次，横纵坐标都要变化，向右上移动的话要坐标加上[-1, 1]，向左下移动的话要坐标加上[1, -1]，那么难点在于我们如何处理越界情况，越界后遍历的方向怎么变换。向右上和左下两个对角线方向遍历的时候都会有越界的可能，但是除了左下角和右上角的位置越界需要改变两个坐标之外，其余的越界只需要改变一个。那么我们就先判断要同时改变两个坐标的越界情况，即在右上角和左下角的位置。如果在右上角位置还要往右上走时，那么要移动到它下面的位置的，那么如果col超过了n-1的范围，那么col重置为n-1，并且row自增2，然后改变遍历的方向。同理如果row超过了m-1的范围，那么row重置为m-1，并且col自增2，然后改变遍历的方向。然后我们再来判断一般的越界情况，如果row小于0，那么row重置0，然后改变遍历的方向。同理如果col小于0，那么col重置0，然后改变遍历的方向。参见代码如下：

 

解法一：

class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return {};
        int m = matrix.size(), n = matrix[0].size(), r = 0, c = 0, k = 0;
        vector<int> res(m * n);
        vector<vector<int>> dirs{{-1,1}, {1,-1}};
        for (int i = 0; i < m * n; ++i) {
            res[i] = matrix[r][c];
            r += dirs[k][0];
            c += dirs[k][1];
            if (r >= m) {r = m - 1; c += 2; k = 1 - k;}
            if (c >= n) {c = n - 1; r += 2; k = 1 - k;}
            if (r < 0) {r = 0; k = 1 - k;}
            if (c < 0) {c = 0; k = 1 - k;}
        }
        return res;
    }
};

 

下面这种方法跟上面的方法思路相同，不过写法有些不同，这里根据横纵左边之和的奇偶性来判断遍历的方向，然后对于越界情况再单独处理即可，参见代码如下：

 

解法二：

class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return {};
        int m = matrix.size(), n = matrix[0].size(), r = 0, c = 0;
        vector<int> res(m * n);
        for (int i = 0; i < m * n; ++i) {
            res[i] = matrix[r][c];
            if ((r + c) % 2 == 0) {
                if (c == n - 1) {++r;}
                else if (r == 0) {++c;}
                else {--r; ++c;}
            } else {
                if (r == m - 1) {++c;}
                else if (c == 0) {++r;}
                else {++r; --c;}
            }
        }
        return res;
    }
};

 

下面这种方法是按遍历方向来按规律往结果res中添加数字的，比如题目中的那个例子，那么添加的顺序如下：

[0,0] -> [0,1],[1,0] -> [2,0],[1,1],[0,2] -> [1,2],[2,1] -> [2,2]

根据遍历的方向不同共分为五层，关键就是确定每一层的坐标范围，其中下边界low = max(0, i - n + 1)，这样可以保证下边界不会小于0，而上边界high = min(i, m - 1)，这样也保证了上边界不会大于m-1，如果是偶数层，则从上边界往下边界遍历，反之如果是奇数层，则从下边界往上边界遍历，注意从matrix中取数字的坐标，，参见代码如下：

 

解法三：

class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return {};
        int m = matrix.size(), n = matrix[0].size(), k = 0;
        vector<int> res(m * n);
        for (int i = 0; i < m + n - 1; ++i) {
            int low = max(0, i - n + 1), high = min(i, m - 1);
            if (i % 2 == 0) {
                for (int j = high; j >= low; --j) {
                    res[k++] = matrix[j][i - j];
                }
            } else {
                for (int j = low; j <= high; ++j) {
                    res[k++] = matrix[j][i - j];
                }
            }
        }
        return res;
    }
};

 

下面这种方法就有一点暴力搜索的感觉，不像上面一种精确计算每一层的坐标范围，这种方法是利用对角线上的数字的横纵坐标之和恒定这一特性来搜索的，然后把和为特定值的数字加入结果res中，参见代码如下：

 

解法四：

class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return {};
        int m = matrix.size(), n = matrix[0].size(), k = 0;
        vector<int> res;
        for (int k = 0; k < m + n - 1; ++k) {
            int delta = 1 - 2 * (k % 2 == 0);
            int ii = (m - 1) * (k % 2 == 0);
            int jj = (n - 1) * (k % 2 == 0);
            for (int i = ii; i >= 0 && i < m; i += delta) {
                for (int j = jj; j >= 0 && j < n; j += delta) {
                    if (i + j == k) {
                        res.push_back(matrix[i][j]);
                    }
                }
            }
        }
        return res;
    }
};

 

参考资料：

https://discuss.leetcode.com/topic/77866/short-bf-solution

https://discuss.leetcode.com/topic/77865/concise-java-solution/2

https://discuss.leetcode.com/topic/77862/my-8ms-short-solution-9line

https://discuss.leetcode.com/topic/77937/java-15-lines-without-using-boolean

 

LeetCode All in One 题目讲解汇总(持续更新中...)

[lld2006]

在一本中文书上看到的这个题的一种写法， 感觉很优雅

class Solution {
public:
    vector findDiagonalOrder(vector>& matrix) {
      vector ret;
      if(matrix.empty() || matrix[0].empty()) return ret;
      int top_row=0, top_col=0, bot_row=0, bot_col=0;    
      int row_size = matrix.size(), col_size = matrix[0].size();
      int from_top_to_bot= 0;
      while(top_row != row_size){
        add_to_vector(top_row, top_col, bot_row, bot_col, from_top_to_bot, ret, matrix);
        top_row = (top_col == col_size-1)? top_row+1:top_row;
        top_col = (top_col == col_size-1)? top_col:top_col+1;
        bot_col = (bot_row == row_size-1) ? bot_col+1: bot_col;
        bot_row = (bot_row == row_size-1) ? bot_row : bot_row+1;
        from_top_to_bot =  1- from_top_to_bot;
      }
      return ret;
    }
    void add_to_vector(int top_row, int top_col, int bot_row, int bot_col, int from_top_to_bot, vector& ret, const vector>& matrix){
      int sum = top_row+top_col;
      if(from_top_to_bot){
        while(top_row <= bot_row){
          ret.push_back(matrix[top_row++][top_col--]);
        }
      }else{
        while(bot_row >=top_row){
          ret.push_back(matrix[bot_row--][bot_col++]);
        }
      }
    }
};