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

shinezejian 发布于2019-08-16 17:54 / 2656人阅读

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

对角线遍历

给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素，对角线遍历如下图所示。
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.
示例:

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

解释:

说明:

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

思路：

实例输入的二维数组范围均是0～2

先观察一下遍历规律：(0,0)->(0,1)->(1,0)->(2,0)->(1,1)->(0,2)->(1,2)->(2,1)->(2,2)

数组索引(m,n)，两种改变方式1、(m-1,n+1) 2、(m+1,n-1)

数组从(0,0)开始，先是(m-1,n+1) ，(0,0)->(-1,1)此时m=-1，超出范围，m赋值0。然后切换索引改变方式(m+1,n-1)，执行两次(0,1)->(1,0)->(2,-1),n赋值0得到(2,0)，再次切换为索引改变方式(m-1,n+1)直到下次超出范围(2,0)->(1,1)->(0,2)->(-1,3)。此时m<0且n>2均超出范围，(m+2,n-1)，应当优先判断n是否超出范围，执行(m+2,n-1)->(1,2)，避免因为m<0再次切换一次索引改变方式。然后正常切换后：(1,2)->(2,1)->(3,0)，因为m>2,切换方式并(m-1,n+2)

java:

class Solution {
    public int[] findDiagonalOrder(int[][] matrix) {
        if (matrix.length==0||matrix[0].length==0)return new int[0];
        int col=matrix.length,row=matrix[0].length;
        int nums=col*row,m=0,n=0;
        int res[]=new int[nums];
        boolean flag=true;

        for(int i=0;i=col){
                m-=1; n+=2; flag=true;
            }else if(n>=row){
                n-=1; m+=2; flag=false;
            }
            if(m<0){
                m=0; flag=false;
            }else if(n<0){
                n=0; flag=true;
            }
        }
        return res;
    }
}

注意点：

if (matrix.length==0||matrix[0].length==0)return new int[0];首先判断是否为空数组，另外 matrix.length==0||matrix[0].length==0 判断条件顺序不能颠倒，因为如果 matrix.length==0 后面的 matrix[0].length==0 不会再判断，即返回空数组；但是matrix[0].length==0 在前时，如果输入数组为空，matrix[0] 会报错因为matrix并没有0号索引。

for循环里应当先判断m、n是否大于或等于各自的最大长度，然后执行(m-1,n+2)、(m+2,n-1)。避免出现m、n同时小于0时flag布尔值转换两次的错误。

python：

class Solution:
    def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]:
        if(len(matrix)==0 or len(matrix[0])==0):
            return []
        col=len(matrix)
        row=len(matrix[0])
        nums=col*row
        m=n=0
        flag=True
        res=[]
        for i in range(nums):
            res.append(matrix[m][n])
            if flag:
                m-=1
                n+=1
            else:
                m+=1
                n-=1
            if m>=col:
                m-=1
                n+=2
                flag=True
            elif n>=row:
                m+=2
                n-=1
                flag=False
            if m<0:
                m=0
                flag=False
            elif n<0:
                n=0
                flag=True
        return res

云服务器 GPU云服务器 python3 遍历 Diagonal Traverse LeetCode

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

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

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

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

olle 2019-07-31 10:31 评论0 收藏0
leetcode498. Diagonal Traverse

摘要：题目要求思路和代码其实这道题目不难，只要捋清楚一些边界的场景即可。自上而下遍历数组时，一定是自右往左移动的，因此下标移动的方向为。自上而下有两种边界场景，一个是到达了左边界，此时的移动方向变为即上图中的。题目要求 Given a matrix of M x N elements (M rows, N columns), return all elements of the matri...

fanux 2019-08-16 18:39 评论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 766 Toeplitz Matrix

摘要：题目详情如果一个矩阵的每一条斜对角线左上到右下上的元素都相等，则我们称它为托普利兹矩阵。现在输入一个大小的矩阵，如果它是一个托普利兹矩阵，则返回，如果不是，返回。题目详情 matrix is Toeplitz if every diagonal from top-left to bottom-right has the same element.Now given an M x N ...

harriszh 2019-08-15 14:02 评论0 收藏0
[Algo] Print Matrix Diagonal 对角打印

摘要：双重循环复杂度时间空间思路总共需要打印的层数，是长度加宽度减去一。关键在于内层的，而。代码计算打印的层数超过边界的点直接跳过 Print Matrix Diagonal Print the matrix in diagonal way. For example: 1 2 3 4 5 6 7 8 Print: 1 2 5 6 3 4 7 8 双重循环复杂度时间 O(NM) 空间...

RancherLabs 2019-08-14 12:47 评论0 收藏0