Leetcode 498:对角线遍历Diagonal Traverse(python3、java)
对角线遍历
给定一个含有 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<nums;i++){ res[i]=matrix[m][n]; if(flag){ n+=1; m-=1; }else{ n-=1; m+=1; } if(m>=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
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
HanLP-最短路径分词
今天介绍的内容是最短路径分词。最近换回了thinkpad x1,原因是mac的13.3寸的屏幕看代码实在是不方便,也可能是人老了吧,^_^。等把HanLP词法分析介绍结束后,还是会换回macbook pro的。个人有强迫症,只要看或写Java或C/C++代码或者用开发机的化,还是喜欢在windows下工作。看论文特别是理论的研究还是习惯用mac了。感觉开发还是windows比较顺手,理论研究还是mac比较顺手。基本思想:首先根据词典,找出字串中所有可能的词(也称全切分),然后构造词语切分有向无环图(也称作粗分词图或粗分词网)。每个词对应图中的一条有向边。若赋给相应的边长一个权值(该权值可以是常数,也可以是所构成的词的属性值),然后根据该切分图,在起点到终点的所有路径中,求出长度值(包括权值)为最短的一条路径,这条路径上包含的词就是该句子的切分结果。若每个结点处记录N个最短路径值,则该方法也称N-最短路径算法。为进一步提高切分精度,在词典中增加词的属性值,即给每个词也给权重。这样每个词在汉字串中的权重不同(即构成的有向图的边不为等长)。最简单的词的权重可以用词频表示,高频词的权重大,低频...
- 下一篇
文件很容易被破解?python带你了解加密解密机制
本节使用python实现了一种简单的加密和解密机制。 描述:使用python实现一个简单的加密和解密机制,使用26个字母和一个单词作为密钥key 秘钥:大写英文字符串 明文:包含空格,大小写字母,数字等的字符串 实现过程 算法过程 主函数 执行主函数 以上就是小编所分享的内容,希望能够帮助到大家,
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
-
Docker使用Oracle官方镜像安装(12C,18C,19C)
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- CentOS8编译安装MySQL8.0.19
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- MySQL8.0.19开启GTID主从同步CentOS8
- CentOS7,8上快速安装Gitea,搭建Git服务器
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
推荐阅读
最新文章
- 2048小游戏-低调大师作品
- Windows10,CentOS7,CentOS8安装MongoDB4.0.16
- Mario游戏-低调大师作品
- CentOS7安装Docker,走上虚拟化容器引擎之路
- CentOS8安装MyCat,轻松搞定数据库的读写分离、垂直分库、水平分库
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
- CentOS7,CentOS8安装Elasticsearch6.8.6
- SpringBoot2初体验,简单认识spring boot2并且搭建基础工程
- CentOS6,CentOS7官方镜像安装Oracle11G
- Docker使用Oracle官方镜像安装(12C,18C,19C)