V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Acceml
V2EX  ›  LeetCode

[Leetcode] 130.被包围的区域

  •  
  •   Acceml ·
    Acceml · 2019-05-26 01:01:18 +08:00 · 14903 次点击
    这是一个创建于 1769 天前的主题,其中的信息可能已经有所发展或是发生改变。

    题目

    给定一个二维的矩阵,包含 'X''O'字母 O)。

    找到所有被 'X' 围绕的区域,并将这些区域里所有的 'O''X' 填充。

    示例:

    X X X X
    X O O X
    X X O X
    X O X X
    

    运行你的函数后,矩阵变为:

    X X X X
    X X X X
    X X X X
    X O X X
    

    解释:

    被围绕的区间不会存在于边界上,换句话说,任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上,或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻,则称它们是“相连”的。

    题解

    这道题我们拿到基本就可以确定是图的 dfs、bfs 遍历的题目了。题目中解释说被包围的区间不会存在于边界上,所以我们会想到边界上的 o 要特殊处理,只要把边界上的 o 特殊处理了,那么剩下的 o 替换成 x 就可以了。问题转化为,如何寻找和边界联通的 o,我们需要考虑如下情况。

    X X X X
    X O O X
    X X O X
    X O O X
    

    这时候的 o 是不做替换的。因为和边界是连通的。为了记录这种状态,我们把这种情况下的 o 换成#作为占位符,待搜索结束之后,遇到 o 替换为 x (和边界不连通的 o);遇到#,替换回 o(和边界连通的 o)。

    如何寻找和边界联通的 o? 从边界出发,对图进行 dfs 和 bfs 即可。这里简单总结下 dfs 和 dfs。

    • bfs 递归。可以想想二叉树中如何递归的进行层序遍历。
    • bfs 非递归。一般用队列存储。
    • dfs 递归。最常用,如二叉树的先序遍历。
    • dfs 非递归。一般用 stack。

    那么基于上面这种想法,我们有四种方式实现。

    dfs 递归

    class Solution {
        public void solve(char[][] board) {
            if (board == null || board.length == 0) return;
            int m = board.length;
            int n = board[0].length;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    // 从边缘 o 开始搜索
                    boolean isEdge = i == 0 || j == 0 || i == m - 1 || j == n - 1;
                    if (isEdge && board[i][j] == 'O') {
                        dfs(board, i, j);
                    }
                }
            }
    
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (board[i][j] == 'O') {
                        board[i][j] = 'X';
                    }
                    if (board[i][j] == '#') {
                        board[i][j] = 'O';
                    }
                }
            }
        }
    
        public void dfs(char[][] board, int i, int j) {
            if (i < 0 || j < 0 || i >= board.length  || j >= board[0].length || board[i][j] == 'X' || board[i][j] == '#') {
                // board[i][j] == '#' 说明已经搜索过了. 
                return;
            }
            board[i][j] = '#';
            dfs(board, i - 1, j); // 上
            dfs(board, i + 1, j); // 下
            dfs(board, i, j - 1); // 左
            dfs(board, i, j + 1); // 右
        }
    }
    

    dfs 非递归

    非递归的方式,我们需要记录每一次遍历过的位置,我们用 stack 来记录,因为它先进后出的特点。而位置我们定义一个内部类 Pos 来标记横坐标和纵坐标。注意的是,在写非递归的时候,我们每次查看 stack 顶,但是并不出 stack,直到这个位置上下左右都搜索不到的时候出 Stack。

    class Solution {
        public class Pos{
            int i;
            int j;
            Pos(int i, int j) {
                this.i = i;
                this.j = j;
            }
        }
        public void solve(char[][] board) {
            if (board == null || board.length == 0) return;
            int m = board.length;
            int n = board[0].length;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    // 从边缘第一个是 o 的开始搜索
                    boolean isEdge = i == 0 || j == 0 || i == m - 1 || j == n - 1;
                    if (isEdge && board[i][j] == 'O') {
                        dfs(board, i, j);
                    }
                }
            }
    
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (board[i][j] == 'O') {
                        board[i][j] = 'X';
                    }
                    if (board[i][j] == '#') {
                        board[i][j] = 'O';
                    }
                }
            }
        }
    
        public void dfs(char[][] board, int i, int j) {
            Stack<Pos> stack = new Stack<>();
            stack.push(new Pos(i, j));
            board[i][j] = '#';
            while (!stack.isEmpty()) {
                // 取出当前 stack 顶, 不弹出.
                Pos current = stack.peek();
                // 上
                if (current.i - 1 >= 0 
                    && board[current.i - 1][current.j] == 'O') {
                    stack.push(new Pos(current.i - 1, current.j));
                    board[current.i - 1][current.j] = '#';
                  continue;
                }
                // 下
                if (current.i + 1 <= board.length - 1 
                    && board[current.i + 1][current.j] == 'O') {
                    stack.push(new Pos(current.i + 1, current.j));
                    board[current.i + 1][current.j] = '#';      
                    continue;
                }
                // 左
                if (current.j - 1 >= 0 
                    && board[current.i][current.j - 1] == 'O') {
                    stack.push(new Pos(current.i, current.j - 1));
                    board[current.i][current.j - 1] = '#';
                    continue;
                }
                // 右
                if (current.j + 1 <= board[0].length - 1 
                    && board[current.i][current.j + 1] == 'O') {
                    stack.push(new Pos(current.i, current.j + 1));
                    board[current.i][current.j + 1] = '#';
                    continue;
                }
                // 如果上下左右都搜索不到,本次搜索结束,弹出 stack
                stack.pop();
            }
        }
    }
    
    

    bfs 非递归

    dfs 非递归的时候我们用 stack 来记录状态,而 bfs 非递归,我们则用队列来记录状态。和 dfs 不同的是,dfs 中搜索上下左右,只要搜索到一个满足条件,我们就顺着该方向继续搜索,所以你可以看到 dfs 代码中,只要满足条件,就入 Stack,然后 continue 本次搜索,进行下一次搜索,直到搜索到没有满足条件的时候出 stack。而 bfs 中,我们要把上下左右满足条件的都入队,所以搜索的时候就不能 continue。大家可以对比下两者的代码,体会 bfs 和 dfs 的差异。

    class Solution {
        public class Pos{
            int i;
            int j;
            Pos(int i, int j) {
                this.i = i;
                this.j = j;
            }
        }
        public void solve(char[][] board) {
            if (board == null || board.length == 0) return;
            int m = board.length;
            int n = board[0].length;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    // 从边缘第一个是 o 的开始搜索
                    boolean isEdge = i == 0 || j == 0 || i == m - 1 || j == n - 1;
                    if (isEdge && board[i][j] == 'O') {
                        bfs(board, i, j);
                    }
                }
            }
    
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (board[i][j] == 'O') {
                        board[i][j] = 'X';
                    }
                    if (board[i][j] == '#') {
                        board[i][j] = 'O';
                    }
                }
            }
        }
    
        public void bfs(char[][] board, int i, int j) {
            Queue<Pos> queue = new LinkedList<>();
            queue.add(new Pos(i, j));
            board[i][j] = '#';
            while (!queue.isEmpty()) {
                Pos current = queue.poll();
                // 上
                if (current.i - 1 >= 0 
                    && board[current.i - 1][current.j] == 'O') {
                    queue.add(new Pos(current.i - 1, current.j));
                    board[current.i - 1][current.j] = '#';
                  	// 没有 continue.
                }
                // 下
                if (current.i + 1 <= board.length - 1 
                    && board[current.i + 1][current.j] == 'O') {
                    queue.add(new Pos(current.i + 1, current.j));
                    board[current.i + 1][current.j] = '#';      
                }
                // 左
                if (current.j - 1 >= 0 
                    && board[current.i][current.j - 1] == 'O') {
                    queue.add(new Pos(current.i, current.j - 1));
                    board[current.i][current.j - 1] = '#';
                }
                // 右
                if (current.j + 1 <= board[0].length - 1 
                    && board[current.i][current.j + 1] == 'O') {
                    queue.add(new Pos(current.i, current.j + 1));
                    board[current.i][current.j + 1] = '#';
                }
            }
        }
    }
    

    bfs 递归

    bfs 一般我们不会去涉及,而且比较绕,之前我们唯一 A 过的用 bfs 递归的方式是层序遍历二叉树的时候可以用递归的方式。

    并查集

    并查集这种数据结构好像大家不太常用,实际上很有用,我在实际的 production code 中用过并查集。并查集常用来解决连通性的问题,即将一个图中连通的部分划分出来。当我们判断图中两个点之间是否存在路径时,就可以根据判断他们是否在一个连通区域。 而这道题我们其实求解的就是和边界的 O 在一个连通区域的的问题。

    并查集的思想就是,同一个连通区域内的所有点的根节点是同一个。将每个点映射成一个数字。先假设每个点的根节点就是他们自己,然后我们以此输入连通的点对,然后将其中一个点的根节点赋成另一个节点的根节点,这样这两个点所在连通区域又相互连通了。 并查集的主要操作有:

    • find(int m):这是并查集的基本操作,查找 m 的根节点。

    • isConnected(int m,int n):判断 m,n 两个点是否在一个连通区域。

    • union(int m,int n):合并 m,n 两个点所在的连通区域。

    class UnionFind {
        int[] parents;
    
        public UnionFind(int totalNodes) {
            parents = new int[totalNodes];
            for (int i = 0; i < totalNodes; i++) {
                parents[i] = i;
            }
        }
    		// 合并连通区域是通过 find 来操作的, 即看这两个节点是不是在一个连通区域内.
        void union(int node1, int node2) {
            int root1 = find(node1);
            int root2 = find(node2);
            if (root1 != root2) {
                parents[root2] = root1;
            }
        }
    
        int find(int node) {
            while (parents[node] != node) {
                // 当前节点的父节点 指向父节点的父节点.
                // 保证一个连通区域最终的 parents 只有一个.
                parents[node] = parents[parents[node]];
                node = parents[node];
            }
    
            return node;
        }
    
        boolean isConnected(int node1, int node2) {
            return find(node1) == find(node2);
        }
    }
    

    我们的思路是把所有边界上的 O 看做一个连通区域。遇到 O 就执行并查集合并操作,这样所有的 O 就会被分成两类

    • 和边界上的 O 在一个连通区域内的。这些 O 我们保留。
    • 不和边界上的 O 在一个连通区域内的。这些 O 就是被包围的,替换。

    由于并查集我们一般用一维数组来记录,方便查找 parants,所以我们将二维坐标用 node 函数转化为一维坐标。

    public void solve(char[][] board) {
            if (board == null || board.length == 0)
                return;
    
            int rows = board.length;
            int cols = board[0].length;
    
            // 用一个虚拟节点, 边界上的 O 的父节点都是这个虚拟节点
            UnionFind uf = new UnionFind(rows * cols + 1);
            int dummyNode = rows * cols;
    
            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < cols; j++) {
                    if (board[i][j] == 'O') {
                        // 遇到 O 进行并查集操作合并
                        if (i == 0 || i == rows - 1 || j == 0 || j == cols - 1) {
                            // 边界上的 O,把它和 dummyNode 合并成一个连通区域.
                            uf.union(node(i, j), dummyNode);
                        } else {
                            // 和上下左右合并成一个连通区域.
                            if (i > 0 && board[i - 1][j] == 'O')
                                uf.union(node(i, j), node(i - 1, j));
                            if (i < rows - 1 && board[i + 1][j] == 'O')
                                uf.union(node(i, j), node(i + 1, j));
                            if (j > 0 && board[i][j - 1] == 'O')
                                uf.union(node(i, j), node(i, j - 1));
                            if (j < cols - 1 && board[i][j + 1] == 'O')
                                uf.union(node(i, j), node(i, j + 1));
                        }
                    }
                }
            }
    
            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < cols; j++) {
                    if (uf.isConnected(node(i, j), dummyNode)) {
                        // 和 dummyNode 在一个连通区域的,那么就是 O ;
                        board[i][j] = 'O';
                    } else {
                        board[i][j] = 'X';
                    }
                }
            }
        }
    
        int node(int i, int j) {
            return i * cols + j;
        }
    }
    

    热门阅读

    Leetcode 名企之路

    CEBBCAT
        1
    CEBBCAT  
       2019-05-26 01:22:25 +08:00 via Android
    建议标题起得有代表性一些,不知你是提问还是分享。

    比较好奇,这文章里的代码是您的吗?
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1016 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 19:31 · PVG 03:31 · LAX 12:31 · JFK 15:31
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.