关注Java领域相关技术 记录有趣的事情

LeetCode-130. 被围绕的区域

US-B.Ralph
US-B.Ralph
2020-08-11

问题地址

LeetCode每日一题/2020-08-11

LeetCode130. 被围绕的区域


问题描述

规则

给定一个二维的矩阵,包含 ‘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’。如果两个元素在水平或垂直方向相邻,则称它们是“相连”的。


解析

解题思路

根据规则任何边界上的O及与之相关联的O都不会被填充为X,所以我们可以分两步操作:
1. 找出边界O及与其相联通的O,并将其标为P。从边界开始遍历矩阵,当边界上的元素[x][y]==’O’时,我们需要判断与其相邻的元素是否为’O’。使用[x][y]表示矩阵中的任意元素,与[x][y]相邻的元素的坐标为:

2. 遍历矩阵将O填充为X,将P填充为O;

复杂度分析:

  1. 时间复杂度分析,第一遍需要找出边界为O且与其相邻为O的元素并标为P,第二遍需要遍历整个矩阵将其中的O填充为X,将其中的P填充为O。所以需要遍历2遍。即O(2rowscols)
  2. 因为在查找及替换过程中均不需要开辟新的空间存储元素。空间复杂度为O(rows*cols)
  3. 综上本题的时间复杂度、空间复杂度为:
    • 时间复杂度为:O(rows*cols);
    • 空间复杂度为:O(rows*cols);

定位问题:

根据规则我们可以将找出被X包围的区域的问题转为找出与边界为O且与之相联通的元素

数据操作分析:

在遍历中填充元素;

  • 首先处理上下边界,即x=[0,xlen);y={0,yLen-1}:
  • 然后处理左右边界,即x={0,xLen-1};y=[1, yLen):

编码实现:

public class Surroundedregions {
    public static void main(String[] args) {
        char[][] chars = {
                {'X', 'O', 'X', 'X'},//x=0
                {'X', 'X', 'O', 'X'},//x=1
                {'X', 'O', 'O', 'X'},//x=2
                {'X', 'X', 'X', 'X'}//x=3
        };
        solve(chars);
    }
    public static void solve(char[][] board) {
        int xLen = board.length;
        if (xLen == 0) return;
        int yLen = board[0].length;

        for (int i = 0; i < yLen; i++) {
            mask(board, 0, i, xLen, yLen);
            mask(board, xLen - 1, i, xLen, yLen);
        }
        for (int i = 1; i < xLen - 1; i++) {
            mask(board, i, 0, xLen, yLen);
            mask(board, i, yLen - 1, xLen, yLen);
        }

        for (int i = 0; i < xLen; i++) {
            for (int j = 0; j < yLen; j++) {
                if (board[i][j] == 'P') {
                    board[i][j] = 'o';//用小写表示被替换过
                } else if (board[i][j] == 'O') {
                    board[i][j] = 'x';
                }
            }
        }
    }
    private static void mask(char[][] board, int x, int y, int xLen, int yLen) {
        if (x < 0 || x >= xLen || y < 0 || y >= yLen || board[x][y] != 'O') return;
        board[x][y] = 'P';
        mask(board, x - 1, y, xLen, yLen);
        mask(board, x, y + 1, xLen, yLen);
        mask(board, x + 1, y, xLen, yLen);
        mask(board, x, y - 1, xLen, yLen);
    }
}

官方解法

  1. 广度优先搜索

– 思路:我们可以使用广度优先搜索实现标记操作。在下面的代码中,我们把标记过的字母 O 修改为字母 A。
– 复杂度分析:
– 时间复杂度:O(n \times m)O(n×m),其中 nn 和 mm 分别为矩阵的行数和列数。广度优先搜索过程中,每一个点至多只会被标记一次。
– 空间复杂度:O(n \times m)O(n×m),其中 nn 和 mm 分别为矩阵的行数和列数。主要为广度优先搜索的队列的开销。

class Solution {
    int[] dx = {1, -1, 0, 0};
    int[] dy = {0, 0, 1, -1};

    public void solve(char[][] board) {
        int n = board.length;
        if (n == 0) {
            return;
        }
        int m = board[0].length;
        Queue<int[]> queue = new LinkedList<int[]>();
        for (int i = 0; i < n; i++) {
            if (board[i][0] == 'O') {
                queue.offer(new int[]{i, 0});
            }
            if (board[i][m - 1] == 'O') {
                queue.offer(new int[]{i, m - 1});
            }
        }
        for (int i = 1; i < m - 1; i++) {
            if (board[0][i] == 'O') {
                queue.offer(new int[]{0, i});
            }
            if (board[n - 1][i] == 'O') {
                queue.offer(new int[]{n - 1, i});
            }
        }
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int x = cell[0], y = cell[1];
            board[x][y] = 'A';
            for (int i = 0; i < 4; i++) {
                int mx = x + dx[i], my = y + dy[i];
                if (mx < 0 || my < 0 || mx >= n || my >= m || board[mx][my] != 'O') {
                    continue;
                }
                queue.offer(new int[]{mx, my});
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 'A') {
                    board[i][j] = 'O';
                } else if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }
    }
}
  1. 深度优先搜索

– 思路:我们可以使用深度优先搜索实现标记操作。在下面的代码中,我们把标记过的字母 O 修改为字母 A。
– 复杂度分析:
– 时间复杂度:O(n \times m)O(n×m),其中 nn 和 mm 分别为矩阵的行数和列数。深度优先搜索过程中,每一个点至多只会被标记一次。
– 空间复杂度:O(n \times m)O(n×m),其中 nn 和 mm 分别为矩阵的行数和列数。主要为深度优先搜索的栈的开销。

class Solution {
    int n, m;

    public void solve(char[][] board) {
        n = board.length;
        if (n == 0) {
            return;
        }
        m = board[0].length;
        for (int i = 0; i < n; i++) {
            dfs(board, i, 0);
            dfs(board, i, m - 1);
        }
        for (int i = 1; i < m - 1; i++) {
            dfs(board, 0, i);
            dfs(board, n - 1, i);
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 'A') {
                    board[i][j] = 'O';
                } else if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }
    }

    public void dfs(char[][] board, int x, int y) {
        if (x < 0 || x >= n || y < 0 || y >= m || board[x][y] != 'O') {
            return;
        }
        board[x][y] = 'A';
        dfs(board, x + 1, y);
        dfs(board, x - 1, y);
        dfs(board, x, y + 1);
        dfs(board, x, y - 1);
    }
}
US-B.Ralph
LeetCode

Leave a Comment

邮箱地址不会被公开。 必填项已用*标注