1. 首页

LeetCode 130. 被围绕的区域

题目描述

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

难度:Middle

前置知识

  • DFS

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

思路

我们需要将所有被X包围的O变成X,并且题目明确说了边缘的所有O都是不可以变成X的。

130.surrounded-regions

其实我们观察会发现,我们除了边缘的O以及和边缘O连通的O是不需要变成X的,其他都要变成X。

经过上面的思考,问题转化为连通区域问题。 这里我们需要标记一下边缘的O以及和边缘O连通的O
我们当然可以用额外的空间去存,但是对于这道题目而言,我们完全可以mutate。这样就空间复杂度会好一点。

整个过程如图所示:

我将边缘的O以及和边缘O连通的O 标记为了 “A”

130.surrounded-regions

关键点解析

  • 二维数组DFS解题模板
  • 转化问题为连通区域问题
  • 直接mutate原数组,节省空间

代码

  • 语言支持:JS,Python3



/* * @lc app=leetcode id=130 lang=javascript * * [130] Surrounded Regions */ // 将O以及周边的O转化为A function mark(board, i, j, rows, cols) { if (i < 0 || i > rows - 1 || j < 0 || j > cols - 1 || board[i][j] !== "O") return; board[i][j] = "A"; mark(board, i + 1, j, rows, cols); mark(board, i - 1, j, rows, cols); mark(board, i, j + 1, rows, cols); mark(board, i, j - 1, rows, cols); } /** * @param {character[][]} board * @return {void} Do not return anything, modify board in-place instead. */ var solve = function(board) { const rows = board.length; if (rows === 0) return []; const cols = board[0].length; for (let i = 0; i < rows; i++) { for (let j = 0; j < cols; j++) { if (i === 0 || i == rows - 1 || j === 0 || j === cols - 1) { mark(board, i, j, rows, cols); } } } for (let i = 0; i < rows; i++) { for (let j = 0; j < cols; j++) { if (board[i][j] === "O") { board[i][j] = "X"; } else if (board[i][j] === "A") { board[i][j] = "O"; } } } return board; };

Python Code:

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        # 如果数组长或宽小于等于2,则不需要替换
        if len(board) <= 2 or len(board[0]) <= 2:
            return

        row, col = len(board), len(board[0])

        def dfs(i, j):
            """
            深度优先算法,如果符合条件,替换为A并进一步测试,否则停止
            """
            if i < 0 or j < 0 or i >= row or j >= col or board[i][j] != 'O':
                return
            board[i][j] = 'A'

            dfs(i - 1, j)
            dfs(i + 1, j)
            dfs(i, j - 1)
            dfs(i, j + 1)

        # 从外围开始
        for i in range(row):
            dfs(i, 0)
            dfs(i, col-1)

        for j in range(col):
            dfs(0, j)
            dfs(row-1, j)

        # 最后完成替换
        for i in range(row):
            for j in range(col):
                if board[i][j] == 'O':
                    board[i][j] = 'X'
                elif board[i][j] == 'A':
                    board[i][j] = 'O'

相关题目

解题模板是一样的

复杂度分析
– 时间复杂度:$O(row * col)$
– 空间复杂度:$O(row * col)$

看完两件小事

如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:

  1. 关注我们的 GitHub 博客,让我们成为长期关系
  2. 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
  3. 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程

JS中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。欢迎热爱技术的你一起加入交流与学习,JS中文网的使命是帮助开发者用代码改变世界

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com

标题:LeetCode 130. 被围绕的区域

链接:https://www.javascriptc.com/4494.html

« 微信小程序登录的前端设计与实现
LeetCode 129. 求根到叶子节点数字之和»
Flutter 中文教程资源

相关推荐

QR code