LeetCode 498 - Diagonal Traverse

https://leetcode.com/problems/diagonal-traverse/

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:

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

X. http://www.cnblogs.com/grandyang/p/6414461.html
这道题给了我们一个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，然后改变遍历的方向
https://discuss.leetcode.com/topic/77865/concise-java-solution

            // 要先判断 大于等于的，否则矩形右上角有问题

一共两个方向：row + 1 && col - 1 || row - 1 && col + 1

先判断是否右或下越界

Walk patterns:

• If out of bottom border (row >= m) then row = m - 1; col += 2; change walk direction.
• if out of right border (col >= n) then col = n - 1; row += 2; change walk direction.
• if out of top border (row < 0) then row = 0; change walk direction.
• if out of left border (col < 0) then col = 0; change walk direction.
• Otherwise, just go along with the current direction.

    public int[] findDiagonalOrder(int[][] matrix) {
        if (matrix == null || matrix.length == 0) return new int[0];
        int m = matrix.length, n = matrix[0].length;
        
        int[] result = new int[m * n];
        int row = 0, col = 0, d = 0;
        int[][] dirs = {{-1, 1}, {1, -1}};
        
        for (int i = 0; i < m * n; i++) {
            result[i] = matrix[row][col];
            row += dirs[d][0];
            col += dirs[d][1];
            
            if (row >= m) { row = m - 1; col += 2; d = 1 - d;}
            if (col >= n) { col = n - 1; row += 2; d = 1 - d;}
            if (row < 0)  { row = 0; d = 1 - d;}
            if (col < 0)  { col = 0; d = 1 - d;}
        }
        
        return result;
    }

https://blog.csdn.net/fuxuemingzhu/article/details/82528226

做法很简单，有两个方向：向右上↗，向左下↙。

然后判断当出界了的时候，下一步应该向哪个方向走就行。因为矩阵的行列对称性，写出来的if语句肯定是对称的。这个可以方便自己写代码以及查错。

    def findDiagonalOrder(self, matrix):

        """

        :type matrix: List[List[int]]

        :rtype: List[int]

        """

        if not matrix or not matrix[0]: return []

        directions = [(-1, 1), (1, -1)]

        count = 0

        res = []

        i, j = 0, 0

        M, N = len(matrix), len(matrix[0])

        while len(res) < M * N:

            if 0 <= i < M and 0 <= j < N:

                res.append(matrix[i][j])

                direct = directions[count % 2]

                i, j = i + direct[0], j + direct[1]

                continue

            elif i < 0 and 0 <= j < N:

                i += 1

            elif 0 <= i < M and j < 0:

                j += 1

            elif i < M and j >= N:

                i += 2

                j -= 1

            elif i >= M and j < N:

                j += 2

                i -= 1

            count += 1

        return res

https://www.jianshu.com/p/23877f1d6af0

我们可以跟随例子中的路线来遍历矩阵，路线无非就是从左下到右上，到顶后又从右上到坐下，一直到最右下角一个点。
在往右上的过程中，一般是行在减，列在加，有三种情况停止右上：

1. 到了第一行，不能再往上了；
2. 到了最右边列，不能再往右了；
3. 到了最右下角的元素，这时候要全部结束遍历。

往左下的过程中，一般是行在加，列在减，有三种情况停止左下：

1. 到了第一列，不能在往左了；
2. 到了最下边的行，不能再往下了；
3. 到了最右下角的元素，这时候要全部结束遍历。

我们把这个过程用代码实现出来就可以了，用多个 if - else 来分支处理。

    public int[] findDiagonalOrder(int[][] matrix) {
        boolean up = true;
        if (matrix.length == 0) return new int[0];
        int[] res = new int[matrix.length * matrix[0].length];
        int i = 0;
        int j = 0;
        for (int k = 0; k < matrix.length * matrix[0].length; k++) {
            res[k] = matrix[i][j];
            if (up) {// 往右上走
                if ((i-1) >= 0 && (j+1) < matrix[0].length) {
                    i--;
                    j++;
                } else if ((j+1) < matrix[0].length) {
                    j++;
                    up = false;
                } else if ((i+1) < matrix.length) {
                    i++;
                    up = false;
                } else break;
            } else {// 往左下走
                if ((i+1) < matrix.length && (j-1) >= 0) {
                    i++;
                    j--;
                } else if ((i+1) < matrix.length) {
                    i++;
                    up = true;
                } else if ((j+1) < matrix[0].length) {
                    j++;
                    up = true;
                } else break;
            }
        }
        return res;
    }

https://medium.com/@lenchen/leetcode-498-diagonal-traverse-7f616ee74ec4
    def findDiagonalOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """

        # approach:
        #     1. if col == n - 1 with up trend (right bolder), or
        # .         col == 0 with down trend (left bolder):
        #               move down, which means row += 1, and turn direction
        #     2. if row == 0 with up trend (top bolder), or
        #           row == m - 1 with down trend (bottom bolder):
        #            move right, which means col += 1 and turn direction
        #     3. Otherwise, go up-right or down-left by direction

        m = len(matrix)
        n = len(matrix[0]) if m > 0 else 0
        if n == 0:
            return []

        result = [0 for i in range(m*n)]
        up = True
        row = col = 0

        for i in range(m*n):
            result[i] = matrix[row][col]

            # check right bolder before top bolder in up trend
            if up:
                if col == n - 1:
                    row = row + 1
                    up =  not up
                elif row == 0:
                    col = col + 1
                    up = not up
                else:
                    row = row - 1
                    col = col + 1

            # check bottom bolder before left bolder in down trend
            else:
                if row == m - 1:
                    col = col + 1
                    up = not up
                elif col == 0:
                    row = row + 1
                    up = not up
                else:
                    row = row + 1
                    col = col - 1

        return result

X.
下面这种方法跟上面的方法思路相同，不过写法有些不同，这里根据横纵左边之和的奇偶性来判断遍历的方向，然后对于越界情况再单独处理即可
https://leetcode.com/problems/diagonal-traverse/discuss/97711/java-15-lines-without-using-boolean

    public int[] findDiagonalOrder(int[][] matrix) {
        if (matrix.length == 0) return new int[0];
        int r = 0, c = 0, m = matrix.length, n = matrix[0].length, arr[] = new int[m * n];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = matrix[r][c];
            if ((r + c) % 2 == 0) { // moving up
                if      (c == n - 1) { r++; }
                else if (r == 0)     { c++; }
                else            { r--; c++; }
            } else {                // moving down
                if      (r == m - 1) { c++; }
                else if (c == 0)     { r++; }
                else            { r++; c--; }
            }   
        }   
        return arr;
    }

X. https://leetcode.com/problems/diagonal-traverse/discuss/97787/Highly-Intuitive-Java-Solution

public int[] findDiagonalOrder(int[][] matrix) {
    if(matrix.length == 0)
        return new int[0];

    int result[] = new int[matrix.length * matrix[0].length];
    int curRow = 0;
    int curCol = 0;
    int index = 0;
    boolean isUp = true;
    for(int i = 0; i < matrix.length + matrix[0].length; i++) {
        if(isUp) {
            while(curRow >= 0 && curCol < matrix[0].length) {
                result[index++] = matrix[curRow--][curCol++];
            }
            if(curCol == matrix[0].length)
                curCol = matrix[0].length - 1;
            curRow = i + 1 - curCol;
            isUp = !isUp;
        }
        else {
            while(curRow < matrix.length && curCol >= 0) {
                result[index++] = matrix[curRow++][curCol--];
            }
            if(curRow == matrix.length)
                curRow = matrix.length - 1;
            curCol = i + 1 - curRow;
            isUp = !isUp;
        }
    }        
    return result;
}

http://bookshadow.com/weblog/2017/02/05/leetcode-diagonal-traverse/

初始对角线方向为右上方（偏移量：行-1, 列+1），遇到边界时转向左下方（偏移量：行+1, 列-1）

对于边界的处理：

向右上方移动遇到上边界时，若未达到右边界，则向右移动（偏移量：行+0，列+1），否则向下移动（偏移量：行+1，列+0）

向左下方移动遇到左边界时，若未达到下边界，则向下移动（偏移量：行+1，列+0），否则向右移动（偏移量：行+0，列+1）

X.

下面这种方法是按遍历方向来按规律往结果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中取数字的坐标

    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中，参见代码如下：

    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;
    }

X.
https://leetcode.com/problems/diagonal-traverse/discuss/97733/C%2B%2B-without-paying-too-much-attention-on-direction-switch

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

    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;
    }




https://blog.csdn.net/Cloudox_/article/details/63262628
我们可以跟随例子中的路线来遍历矩阵，路线无非就是从左下到右上，到顶后又从右上到坐下，一直到最右下角一个点。

在往右上的过程中，一般是行在减，列在加，有三种情况停止右上：

到了第一行，不能再往上了；
到了最右边列，不能再往右了；
到了最右下角的元素，这时候要全部结束遍历。
往左下的过程中，一般是行在加，列在减，有三种情况停止左下：

到了第一列，不能在往左了；
到了最下边的行，不能再往下了；
到了最右下角的元素，这时候要全部结束遍历。
我们把这个过程用代码实现出来就可以了，用多个 if - else 来分支处理。

  public int[] findDiagonalOrder(int[][] matrix) {

    boolean up = true;

    if (matrix.length == 0)

      return new int[0];

    int[] res = new int[matrix.length * matrix[0].length];

    int i = 0;

    int j = 0;

    for (int k = 0; k < matrix.length * matrix[0].length; k++) {

      res[k] = matrix[i][j];

      if (up) {// 往右上走

        if ((i - 1) >= 0 && (j + 1) < matrix[0].length) {

          i--;

          j++;

        } else if ((j + 1) < matrix[0].length) {

          j++;

          up = false;

        } else if ((i + 1) < matrix.length) {

          i++;

          up = false;

        } else

          break;

      } else {// 往左下走

        if ((i + 1) < matrix.length && (j - 1) >= 0) {

          i++;

          j--;

        } else if ((i + 1) < matrix.length) {

          i++;

          up = true;

        } else if ((j + 1) < matrix[0].length) {

          j++;

          up = true;

        } else

          break;

      }

    }

    return res;

  }