Leetcode: 【每日一题】- 2019-12-26 - 498. 对角线遍历

[azl397985856]

给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素，对角线遍历如下图所示。

 

示例:

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

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

解释:

 

说明:

给定矩阵中的元素总数不会超过 100000 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/diagonal-traverse
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[azl397985856]

Python Solution

对于

1 2 3
4 5 6
7 8 9

我们不考虑换方向，假设题目不要求我们变换方向，对于上图我们的遍历结果就是：

1
2 4
3 5 7
6 8
9

这种做法比较简单，我们只要找出每一次需要遍历的起始元素，然后不断找到左下角，直到越界即可。

然后我们回到题目的要求，题目要求我们不断变换次序，那么一种简单的做法就是对于偶数次遍历我们都进行一次反转即可。如上：

1 (reverse)
2 4
7 5 3 (reverse)
6 8
9 (reverse)

Code

#
# @lc app=leetcode.cn id=498 lang=python3
#
# [498] 对角线遍历
#

# @lc code=start


class Solution:
    # 1 2 3
    # 4 5 6
    # 7 8 9
    def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]:
        direction = 'UP'
        m = len(matrix)
        if m == 0:
            return []
        n = len(matrix[0])
        temp = []
        res = []
        for j in range(n):
            i = 0
            direction = 'DOWN' if direction == 'UP' else 'UP'
            while i < m and j >= 0:
                temp.append(matrix[i][j])
                i += 1
                j -= 1
            if direction == 'DOWN':
                temp.reverse()
            res += temp
            temp = []
        for i in range(1, m):
            j = n - 1
            direction = 'DOWN' if direction == 'UP' else 'UP'
            while i < m and j >= 0:
                temp.append(matrix[i][j])
                i += 1
                j -= 1
            if direction == 'DOWN':
                temp.reverse()
            res += temp
            temp = []
        return res

        # @lc code=end

[threedayAAAAA]

判断边界

class Solution {

    public int[] findDiagonalOrder(int[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return new int[0];
        }
        int iNum  = matrix.length;
        int jNum = matrix[0].length;
        int[] result = new int[iNum*jNum];
        boolean isUp = true;
        int resultIndex = 0;
        int iIndex = 0,jIndex = 0;
        while(iIndex < iNum && jIndex < jNum){//边界控制
            if(isUp){
                while(iIndex >=0 && jIndex >=0 && iIndex < iNum && jIndex <jNum){//遍历上升的所有数
                    result[resultIndex++] = matrix[iIndex--][jIndex++];
                }
                iIndex++;jIndex--;//reert，上面退出循环后多改变了一次，要先还原到up的最后一个元素的index状态
                if(jIndex+1 < jNum){//先j+1；
                    jIndex++;
                }else{//j会超过边界，此时i+1;
                    iIndex++;
                }
                isUp = false;
            }else{
                while(iIndex >=0 && jIndex >=0 && iIndex < iNum && jIndex <jNum){//遍历下降的所有数
                    result[resultIndex++] = matrix[iIndex++][jIndex--];
                }
                iIndex--;jIndex++;//revert，和up的解释相同
                if(iIndex + 1 < iNum){//先i+1
                    iIndex++;
                }else{//i会超出边界，此时j+1
                    jIndex++;
                }
                isUp = true;
            }
        }
        return result;
    }

}

[HEternally]

var findDiagonalOrder = function(matrix) {
    // 设m为纵坐标，n为横坐标
    // 据题意可知，当m+n为奇数时向下遍历，m+n为偶数时向上遍历

    // 遍历方式
    // 向上遍历时：m递减，n递增
    // 向下遍历时：m递增，n递减
    // 以此循环

    /** 遍历结束条件
     *  向上遍历：m递减到0或者n递增到最大值
     *  向下遍历：n递减到0或者m递增到最大值
     */

    // 初始化返回值
    let res = [];
    let m = matrix.length;
    // 判断输入值长度为0直接返回
    if (m === 0 || (m > 0 && matrix[0].length === 0)) return res;
    let n = matrix[0].length;
    // 定义Boolean traversal值为此时的遍历方式为向上还是向下
    let traversal = true;

    for (let i = 0; i < m + n - 1; i++) {
    let pm = traversal ? m : n;
    let pn = traversal ? n : m;

    let x = (i < pm) ? i : pm - 1;
    let y = i - x;                

    while (x >= 0 && y < pn) {
        res.push(traversal ? matrix[x][y] : matrix[y][x]);
        x--;
        y++;
    }
    raversal = !traversal;
    }
    return res;
};

[18sby]

var findDiagonalOrder = function(matrix) {
  let m = matrix.length;
  if (m === 0) return matrix;

  let n = matrix[0].length;
  if (n === 0) return matrix;

  let flag = true, ans = [];
  for (let i = 0; i < m + n - 1; i++) {
    if (flag) {
      let x = i < m ? i : m - 1,
          y = i - x;

      while (x >= 0 && y < n) {
        ans.push( matrix[x][y] );
        x--;
        y++;
      }
    }
    else {
      let y = i < n ? i : n - 1,
          x = i - y;

      while (y >= 0 && x < m) {
        ans.push( matrix[x][y] );
        y--;
        x++;
      }
    }

    flag = !flag;
  }

  return ans;
};