乐趣区

关于前端:美团二面算法题沿对角线遍历二维数组

美团二面的时候面试官出了这道题,一起来看下:

实现一个函数,沿对角线遍历二维数组

例如:
[
[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;
}

xy 示意以后元素的坐标,nm 别离代表 arr.length-1arr[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…

退出移动版