leetcode498. Diagonal Traverse

fanux 发布于2019-08-16 18:39 / 432人阅读

摘要：题目要求思路和代码其实这道题目不难，只要捋清楚一些边界的场景即可。自上而下遍历数组时，一定是自右往左移动的，因此下标移动的方向为。自上而下有两种边界场景，一个是到达了左边界，此时的移动方向变为即上图中的。

题目要求

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]

思路和代码

其实这道题目不难，只要捋清楚一些边界的场景即可。自上而下遍历数组时，一定是自右往左移动的，因此下标移动的方向为[row, column]=>[row+1, column-1]。自上而下有两种边界场景，一个是到达了左边界，此时的移动方向变为[row, column]=>[row+1, column], 即上图中的4->7。另一个是遇到了下边界，此时的移动方向变为[row, column]=>[row, column+1]，即上图中的8->9。同理，自下而上遍历数组时，一定是自左往右移动的，因此下标的移动方向为[row, column]=>[row-1, column+1]。它同样有两个边界场景，一个是到达了右边界，此时的移动方向变为[row, column]=>[row+1, column]，还有一个场景是遇到上边界，此时的移动方向变为[row, column]=>[row, column+1]。

上述思路的代码如下：

    public int[] findDiagonalOrder(int[][] matrix) {
        if(matrix==null || matrix.length==0 || matrix[0].length==0) return new int[0];
        int row = matrix.length;
        int column = matrix[0].length;
        int[] result = new int[row * column];
        int rowIndex = 0;
        int columnIndex = 0;
        boolean up = true;
        int index = 0;
        while(index < result.length) {
            result[index++] = matrix[rowIndex][columnIndex];
            if(up) {
                if(rowIndex > 0 && columnIndex < column-1) {
                    rowIndex--;
                    columnIndex++;
                }else {
                    up = false;
                    if(columnIndex < column-1){
                        columnIndex++;
                    }else {
                        rowIndex++;
                    }
                }
                    
            }else {
                if(rowIndex < row-1 && columnIndex > 0) {
                    rowIndex++;
                    columnIndex--;
                }else{
                    up = true;
                    if(rowIndex < row-1) {
                        rowIndex++;
                    }else {
                        columnIndex++;
                    }
                }
            }
        }
        return result;
    }

GPU云服务器云服务器 Diagonal Traverse Leetcod LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/75520.html

Leetcode 498：对角线遍历Diagonal Traverse（python3、java）

摘要：对角线遍历给定一个含有个元素的矩阵行，列，请以对角线遍历的顺序返回这个矩阵中的所有元素，对角线遍历如下图所示。此时且均超出范围，，应当优先判断是否超出范围，执行，避免因为再次切换一次索引改变方式。避免出现同时小于时布尔值转换两次的错误。对角线遍历给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素，对角线遍历如下图所示。Given ...

olle 2019-07-31 10:31 评论0 收藏0
Leetcode 498：对角线遍历Diagonal Traverse（python3、java）

摘要：对角线遍历给定一个含有个元素的矩阵行，列，请以对角线遍历的顺序返回这个矩阵中的所有元素，对角线遍历如下图所示。此时且均超出范围，，应当优先判断是否超出范围，执行，避免因为再次切换一次索引改变方式。避免出现同时小于时布尔值转换两次的错误。对角线遍历给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素，对角线遍历如下图所示。Given ...

shinezejian 2019-08-16 17:54 评论0 收藏0
Diagonal traverse

Diagonal traverse 题目链接：https://leetcode.com/contest/... 就是找index的规律。。 public class Solution { public int[] findDiagonalOrder(int[][] matrix) { if(matrix == null || matrix.length == 0 || ma...

DevTalking 2019-08-14 17:21 评论0 收藏0
[LeetCode] 348. Design Tic-Tac-Toe

Problem Design a Tic-tac-toe game that is played between two players on a n x n grid. You may assume the following rules: A move is guaranteed to be valid and is placed on an empty block.Once a winnin...

MobService 2019-08-16 13:51 评论0 收藏0
[LeetCode] 562. Longest Line of Consecutive One in

Problem Given a 01 matrix M, find the longest line of consecutive one in the matrix. The line could be horizontal, vertical, diagonal or anti-diagonal.Example:Input:[[0,1,1,0], [0,1,1,0], [0,0,0,1]]Ou...

tomlingtm 2019-08-16 13:54 评论0 收藏0