首页 > 其他分享 >[LeetCode] 498. Diagonal Traverse 对角线遍历

[LeetCode] 498. Diagonal Traverse 对角线遍历

时间:2023-12-06 14:02:46浏览次数:35  
标签:Traverse mat ++ Diagonal 498 对角线 移动 col row

题目

Given an m x n matrix mat, return an array of all the elements of the array in a diagonal order.
image

思考

最初在纸上写写画画试了很多想法,但都没能解决,真的。。太弱了T T。
后来在YT上看了个印度老哥的题解才醍醐灌顶。在此尝试复述他的题解。

这题就是说将一个二维矩阵按照对角线的形式遍历。

其实输出什么内容直觉很快就能反应过来。
但真正困难的地方在于如何将这个对角线的输出过程具体描述出来
包括如何确定移动的方向?如何移动?在什么条件下要移向下一行对角线?
如果能将这道题分解为上述三个小问,解题难度则会下降很多。

确定移动方向

移动方向很简单,无非就是向上和向下,可以用一个flag判断上下。

对角线中移动的过程

那么这个对角线移动具体是怎么移动的呢?
我们可以参考example1这个图:
假设我们现在在 '7',接下来要移动到 '5',那就是(3,1) -> (2,2)
假设我们在 '6',接下来要移动到 '8',那就是(2,3) -> (3,2)
用这两个向上、向下的例子我们可以看出向上就意味着row--, col++(向上一行,向右一列),向下则反过来 row++, col--(向下一行,向左一列)。

移动到下一条对角线

对于怎样移动到下一条对角线,第一直觉肯定是“当碰到边界时就向下一条对角线移动”
这是个很好的直觉
我们可以在这个直觉的基础上细化思考“怎样定义边界条件?”“怎样移动到下一条对角线?”

边界条件

看图我们可以总结出:在row, col加加减减的过程中,当他们超过了m或者n就换行了。
但很明显,这个边界条件是分上下方向的,非常简单却不能忽略。
向上:row < m || col > n - 1
向下:col < n || row > m - 1

向下一条对角线移动

实际上是一条对角线的终点移动到下一条对角线的起点。
对于方向向上
移动过程是row--, col++,当我们移动到最后一列时没法再继续移动列,所以向下移动一行。而还没到最后一列时,我们继续移动一列
而对于方向向下则与之相反。

代码实现

上面的问题都分析清楚后,就可以写题解了

class Solution {
    public int[] findDiagonalOrder(int[][] mat) {
	//首先判断矩阵为0的情况
	if (mat.length == 0 || mat[0].length == 0) return new int[0];
	//初始化
	int m = mat.length; //矩阵行长度
	int n = mat[0].length; //矩阵列长度
	int[] arr = new int[m*n]; //存对角遍历结果的数组
	int i = 0; //数组的计数
	boolean up = true; //判定方向的flag
	int row = 0, col = 0; //定义当前指向的矩阵位置,从(0,0)开始
	while (row < m && col < n) {
		//方向向上
		if (up) {
		//移动
		while (row > 0 || col < n - 1) {
			arr[i++] = mat[row][col];
			row--;
			col++;
		}
		//移动到边界时会跳出循环,但边界数字还是要压入数组中
		arr[i++] = mat[row][col];
		//同时判断边界情况,是否到达了最后一列
		if (col == n - 1) {
			row++;
		} else {
			col++;
		}
		} else {
		while (col > 0 || row < m - 1) {
			arr[i++] = mat[row][col];
			row++;
			col--;
		}
		arr[i++] = mat[row][col];
		//判断边界情况,是否到达最后一行
		if (row = m - 1) {
			col++;
		} else {
			row++;
		}
		}
		//换到下一条对角线时,方向要变化
		up = !up;
	}
	return arr;
	}
}

总结

代码实现起来其实很简答。难的是在对这个对角线遍历的建模。
如何把自己直觉式的解决方法转化成计算机能执行的代码是相当不容易的。
而从这道题中,我觉得将大问题分解成小问题再逐个击破是一个很好的方法~

标签:Traverse,mat,++,Diagonal,498,对角线,移动,col,row
From: https://www.cnblogs.com/zoexcode/p/17879212.html

相关文章

  • http://localhost:xxxxx/sockjs-node/info?t=1699323049868
    http://localhost:xxxxx/sockjs-node/info?t=1699323049868 sockjs-node是一个JavaScript库,提供跨浏览器JavaScript的API,创建了一个低延迟、全双工的浏览器和web服务器之间通信通道。解决办法: 配置devServer,然后重启项目1.在vue.config.js中找到devServer中加入 host:'l......
  • 用友U8出纳管理操作提示集合中的498483已经加锁了,不能对集合中的数据进行加锁
    模块:出纳管理服务器上面登录数据库管理平台,选中相应的账套库执行语句deletefromCN_LockAcctbook;......
  • CF498B Name That Tune
    好像和题解不太一样。令\(f_{i,j}\)为第\(j\)秒末识别出第\(i\)首歌的概率。那么答案就是\(\sum\limits_{i=1}^n\sum\limits_{j=1}^Tf_{i,j}\)。转移分两种:听完了这首歌都没识别出,此时算是识别出这首歌了,\(f_{i,j}\getsf_{i-1,j-t_i}\cdot(1-p_i)^{t_i}\)。听到一半......
  • OGG-06498 trail文件满问题
    OGG12.1及以前的版本巡检时发现ogg传输进程异常报错如下:2021-12-0916:25:19ERROROGG-06498Thesequencenumber998999foroutputtrailfile‘/data/ggs/dirdat/tp’hasexceededthemaximumthreshold(998999).PleaseconsultOracleKnowledgeManagementDocID1559......
  • CF498A题解
    简单解析几何。做这道题之前,你需要知道:根据两点求直线一般式。根据两条直线求交点坐标。这里直接丢公式了,百度上也有证明过程,自己推导难度也不大。若两点坐标为\((x_1,y_1),(x_2,y_2)\),则直线方程为:\(Ax+By+C=0\),其中\(A=y_2-y_1,B=x_1-x_2,C=x_2y_1-x_1y_2\)。......
  • P9498 「RiOI-2」equals题解
    题目传送门:P9498「RiOI-2」equals-洛谷|计算机科学教育新生态(luogu.com.cn)这是洛谷月赛Div.2T3,由于我比较菜,只能赛场上切到T3(T4是黑。),开题我们很容易就看出这道题首先需要初始化每个点到根节点的最短路,而且边权都为1,所以我们先无脑打一个堆优化的dijkstra,剩下的就是处......
  • Codeforces[CF1036B]Diagonal Walking v.2题解
    题目大意很明显,这道题就是求k步之内到达点\((a,b)\),然后尽量走对角线,求能走对角线的最大值。做题思路首先明白一个事实,即一个对角线可以通过增加一步而抵达点不变,如图:我们可以这样思考这道题,在到达目的地以后,剩余步数如果为双数,则在对角线来回走,最后会到目的地。但如果剩......
  • POJ 3498 March of the Penguins(枚举+最大流)
    题意:在X,Y坐标系中有N(N<=100)个冰块...有些冰块上有若干只企鹅..每只企鹅一次最多跳M距离..一个冰块在有Mi个企鹅离开..就会消失..问有哪些冰块可以作为集合点..就是所有企鹅都能成功到这个冰块上来.思路:枚举每一块冰块,看看最大流能否等于企鹅总数即可      建图:把每块......
  • P3498 [POI2010]KOR-Beads 题解
    前言:最近在做哈希的题,发现了这道好题,看题解里很多大佬的方法都很巧妙,自己就发一个较为朴素的方法吧。题意:题目传送门给你一个序列,需要求出数k,使划分的子串长度为k时,不同的子串数量最多。还要注意几件事:子串可以反转,比如(1,2,3)看做与(3,2,1)相同。如果不能正好划......
  • (ADI)AD7276ARMZ高速模数转换器、A4980KLPTR汽车步进电机驱动器
    AD7276ARMZ是(ADI)的高速模数转换器、数模转换器和AFE/CODEC构成了业界知名的高速数据转换器产品组合。该器件具有出色性能、高输入带宽和集成的信号处理,使设计人员能够轻松、可靠地选择合适的方案用于各种应用,包括仪表、军用/航天、无线/有线通信和医学影像。位数:12采样率(每......