498.對角線遍歷

https://leetcode.cn/problems/diagonal-traverse/solution/by-qingfengpython-h6zl/

難度：中等

題目：

給你一個(gè)大小為 m x n 的矩陣 mat ，請以對角線遍歷的順序，用一個(gè)數(shù)組返回這個(gè)矩陣中的所有元素。

提示：

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 104
• 1 <= m * n <= 104
• -10^5 <= mat[i][j] <= 10^5

示例：

示例 1：

輸入：mat = [[1,2,3],[4,5,6],[7,8,9]]
輸出：[1,2,4,7,5,3,6,8,9]
示例 2：

輸入：mat = [[1,2],[3,4]]
輸出：[1,2,3,4]

分析

一道邏輯比較簡單的模擬題目，可以不必考慮太多，僅關(guān)注 移動(dòng)方向、邊界 這兩個(gè)問題即可。

1. 起始點(diǎn)為row,col = [0,0]，這個(gè)很明確
2. 矩陣掃描的方向有兩個(gè)[(1, -1), (-1, 1)],即左下↙，和右上↗。
3. 掃描方向?yàn)橛疑熄J，且坐標(biāo)處于矩陣頂部和右邊界時(shí)，當(dāng)col未抵達(dá)右邊界時(shí)，向右走一格，否則則向下走一格，并且轉(zhuǎn)向左下↙
4. 掃描方向?yàn)樽笙篓L，且坐標(biāo)處于矩陣左邊界和底部時(shí)，當(dāng)row未抵達(dá)底部時(shí)，向下走一格，否則向右走一格，并且轉(zhuǎn)向右上↗
5. 循環(huán)執(zhí)行3、4，直至走到矩陣末端結(jié)束循環(huán)即可。

[圖片上傳失敗...(image-77cac8-1662294937592)]

解題：

Python:

class Solution:
    def findDiagonalOrder(self, mat):
        choice = [(1, -1), (-1, 1)]
        row, col, row_max, col_max, direction = 0, 0, len(mat), len(mat[0]), 1
        ret = []
        while row < row_max and col < col_max:
            ret.append(mat[row][col])
            if direction == 1 and (row == 0 or col == col_max - 1):
                direction = 0
                if col < col_max - 1:
                    col += 1
                else :
                    row += 1
            elif direction == 0 and (col == 0 or row == row_max - 1):
                direction = 1
                if row < row_max - 1:
                    row += 1
                else :
                    col += 1
            else:
                row += choice[direction][0]
                col += choice[direction][1]
        return ret

Java:

class Solution {
    public int[] findDiagonalOrder(int[][] mat) {
        int row = 0, col = 0, row_max = mat.length, col_max = mat[0].length;
        int index = 0, direction = 1;
        int[][] choice = {{1, -1}, {-1, 1}};
        int[] ret = new int[row_max * col_max];
        while (row < row_max && col < col_max) {
            ret[index++] = mat[row][col];
            if (direction == 1 && (row == 0 || col == col_max - 1)) {
                direction = 0;
                if (col < col_max - 1) {
                    col++;
                } else {
                    row++;
                }
            } else if (direction == 0 && (col == 0 || row == row_max - 1)) {
                direction = 1;
                if (row < row_max - 1) {
                    row++;
                } else {
                    col++;
                }
            } else {
                row += choice[direction][0];
                col += choice[direction][1];
            }
        }
        return ret;
    }
}

歡迎關(guān)注我的公_眾號: 清風(fēng)Python，帶你每日學(xué)習(xí)Python算法刷題的同時(shí)，了解更多python小知識。

我的個(gè)人博客：https://qingfengpython.cn

力扣解題合集：https://github.com/BreezePython/AlgorithmMarkdown