LeetCode Weekly Contest 24 之 542.01 Matrix

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434834

LeetCode Weekly Contest 24

赛题

本次周赛主要分为一下4道题：

• 543 Diameter of Binary Tree (4分)
• 538 Convert BST to Greater Tree (6分)
• 542 01 Matrix (7分)
• 544 Output Contest Matches (7分)

542 01 Matrix

Problem:

Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell. The distances between two adjacent cells is 1.

Example 1:

Input: 000010000 \begin{matrix} 0 & 0 & 0 \ 0 & 1 & 0 \ 0 & 0 & 0 \ \end{matrix}undefined Output: 000010000 \begin{matrix} 0 & 0 & 0 \ 0 & 1 & 0 \ 0 & 0 & 0 \ \end{matrix}

Example 2:

Input: 001011001 \begin{matrix} 0 & 0 & 0 \ 0 & 1 & 0 \ 1 & 1 & 1 \ \end{matrix}undefined Output: 001012001 \begin{matrix} 0 & 0 & 0 \ 0 & 1 & 0 \ 1 & 2 & 1 \ \end{matrix}

Note:

• The number of elements of the given matrix will not exceed 10,000.
• There are at least one 0 in the given matrix.
• The cells are adjacent in only four directions: up, down, left and right.

我的思路永远是复杂的，也不知道为啥，难道是受其他题目的影响，还是做的不够多，见识不够广咧。第一反映居然是dfs，刚开始不以为然，不就是从某个位置为1开始，从四个方向找最近的零元素么！但当提交代码后才发现，我去，最近0元素未必一定是在它遍历的四个方向上，遍历可以拐弯！那dfs怎么做？至少我所知道的dfs压根没法解决递归过程中改变方向的问题。

唉，所以又得换思路了，而bfs在我脑海中未成型，很难想到它的应用，自然也就无法形成答案。所以我是照着discuss中的bfs解决方案来模拟它的求解过程的，方便自己理解。我们直接拿第二个例子来解释。

解决思路

1. 对待求矩阵进行一次变换，遇0元素不变，遇1元素设为最大值。 00inf0infinf00inf \begin{matrix} 0 & 0 & 0 \ 0 & inf & 0 \ inf & inf & inf \ \end{matrix}

inf在此处表示无穷，在Java代码中，用Integer.MAX_VALUE来表示。在对它变换的同时，由于已经扫描了一遍矩阵，在此过程中还需要记录所有0元素的row,col值，并放入一个队列中。

接下来是求解的核心了，我们只需要寻找到一种机制能够准确更新该数组就可以了，并且它的更新规则符合题意。刚才的dfs是在一个方向上遍历到底，没法拐弯，问题的关键在于隔壁的1元素是否携带了有效信息供当前节点参考！很明显，dfs方案一条路走到底，每个1元素忽略另外三个方向的信息，所以自然而然无法求出正确的。

而再来看看bfs，用形象的比喻来描述这道题的话，就是一颗石头扔入湖中时，它的影响波及周围，且向四周不断传播它的影响。所以该算法的思想，就是首先把这些石头找出来咯【0元素】，更新规则是，一旦碰到【inf】，我就设一个该【0元素】对【inf】的影响值，此处为1。但由于【0元素】的影响是传递的，所以受它影响的【inf】节点必须得放入队列中，计算下次影响值。碰到【inf】，则+1，但前提是当前【inf】节点的值大于原先的值+1。

第二次更新：

00101inf001

\begin{matrix} 0 & 0 & 0 \ 0 & 1& 0 \ 1& inf & 1\ \end{matrix}

0元素周围的元素均被波及，接下来就是1元素的传递，传递的还是0元素的影响。

第三次更新：

001012001

\begin{matrix} 0 & 0 & 0 \ 0 & 1& 0 \ 1& 2& 1\ \end{matrix}

My first solution(119ms)

public List<List<Integer>> updateMatrix(List<List<Integer>> matrix) {
        int m = matrix.size();
        int n = matrix.get(0).size();

        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix.get(i).get(j) == 0) {
                    queue.offer(new int[] {i, j}); //把0元素加入队列中，以备波及影响周围元素
                }
                else {
                    matrix.get(i).set(j, Integer.MAX_VALUE);//设为最大值，方便求0元素影响值
                }
            }
        }
        //溅起的涟漪，代表传播的四个方向
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};


        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            for (int[] d : dirs) {
                //需要比较的下一位置元素
                int r = cell[0] + d[0];
                int c = cell[1] + d[1];
                //不符合条件的均跳过，找来的比如：0 的周围 还是0的哪些元素，1的周围是1，但不符合影响值更新规则的同样忽略。
                if (r < 0 || r >= m || c < 0 || c >= n || 
                    matrix.get(r).get(c) <= matrix.get(cell[0]).get(cell[1]) + 1) continue;
                //把受0波及的1元素也放入队列中，涟漪是会持续的。
                queue.add(new int[] {r, c});
                matrix.get(r).set(c, matrix.get(cell[0]).get(cell[1]) + 1);
            }
        }

        return matrix;
    }

好了，现在代码是不是就容易理解了，该问题的核心思想就是bfs的涟漪传播，解决方案只能说太妙了，不看答案想不到。但反过头来看看bfs和dfs，是不是也能比较出一些区别了呢？起码这道题加深了我对bfs的认知，以及理解了dfs的局限性。