美团二面的时候面试官出了这道题,一起来看下:
实现一个函数,沿对角线遍历二维数组
例如:
[
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
打印输出:
[3, 2, 6, 1, 5, 9, 4, 8, 7]
之前没碰到过对角线遍历的,只做过 Leetcode 48 旋转图像 这样找法则的题。过后没想进去,只写了个伪代码大抵说了下思路(还望面试官手下留情 😅)。昨天在解 N 皇后
问题的时候,须要遍历二维数组对角线上的元素,这道题忽然来了思路,上面把解题思路跟大家分享下。
这道题的外围就是要实现一个函数 diagonalTraverse
,给定某个元素坐标,而后沿着右下角的方向进行遍历。例如给定的元素是 2,那就按 2 -> 6 的程序进行遍历;给定的元素是 1,按 1 -> 5 -> 9 的程序遍历。
右下角方向遍历其实很简略,每次给以后元素的横坐标和纵坐标别离 + 1,就能够实现了,diagonalTraverse
函数的实现如下:
public List<Integer> diagonalTraverse(int x, int y, int n, int m) {List<Integer> list = new ArrayList<>();
while (x <= n && y <= m) {list.add(arr[x][y]);
x++;
y++;
}
return list;
}
x
和y
示意以后元素的坐标,n
和m
别离代表arr.length-1
和arr[0].length-1
在遍历的时候要留神不能越界
有了这个函数之后,咱们只有依照下图从右到左,从上到下的程序给它传入边界元素坐标,就能够实现题目要求的对角线遍历的成果了。
从上图能够看进去,传入坐标的时候分两次比拟好解决,第一次遍历程度方向(3 -> 2 -> 1),第二次遍历垂直方向(4 -> 7)。flatArray
函数的实现如下:
public List<Integer> flatArray(int[][] matrix) {
this.arr = matrix;
final int n = arr.length - 1;
final int m = arr[0].length - 1;
List<Integer> res = new ArrayList<>(); // 保留遍历后果
for (int i=m; i>=0; i--) {
// 遍历程度方向
List<Integer> list = diagonalTraverse(0, i, n, m);
res.addAll(list);
}
for (int i=1; i<=n; i++) {
// 遍历垂直方向
List<Integer> list = diagonalTraverse(i, 0, n, m);
res.addAll(list);
}
return res;
}
明天的文章就到这里,残缺代码能够看我的 GitHub:
https://github.com/Jiacheng78…