☆打卡算法☆LeetCode 130. 被围绕的区域 算法解析

恬静的小魔龙 发表于 2022/06/29 11:21:52 2022/06/29
【摘要】 推荐阅读CSDN主页GitHub开源地址Unity3D插件分享简书地址我的个人博客QQ群:1040082875大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。 一、题目 1、算法题目“给定一个矩阵,矩阵由字符X和O组成,找出所有被X包围的区域,将区域内的所有O替换成X。”题目链接:来源:力扣(LeetCode)...

推荐阅读

大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定一个矩阵,矩阵由字符X和O组成,找出所有被X包围的区域,将区域内的所有O替换成X。”

题目链接:

来源:力扣(LeetCode)

链接: 130. 被围绕的区域 - 力扣(LeetCode) (leetcode-cn.com)

2、题目描述

给你一个 m x n 的矩阵 board ,由若干字符 'X' 和 'O' ,找到所有被 'X' 围绕的区域,并将这些区域里所有的 'O' 用 'X' 填充。

image.png

示例 1:
输入:board = [["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'。如果两个元素在水平或垂直方向相邻,则称它们是“相连”的。
示例 2:
输入: board = [["X"]]
输出: [["X"]]

二、解题

1、思路分析

本题要求将所有被字母X包围的字母O都变成X,所以要找出那些O是被包围的。

题意中有说,任何边界的O都不会被X包围,也就是说,对于每一个边界上的O,以它为起点,标记所有与它直接或间接相连的O,遍历这个矩阵,对于每一个字母:

  • 如果该字母被标记过,则该字母不被包围,将其改成字母O
  • 如果该字母没有被标记,则该字母被包围,将其改成字母X

OK,思路有了,接下来就是使用深度优先算法去遍历搜索实现标记操作。

2、代码实现

代码参考:

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);
    }
}

image.png

3、时间复杂度

时间复杂度:O(n * m)

其中n和m分别是矩阵的行数和列数。

空间复杂度:O(n * m)

其中n和m分别是矩阵的行数和列数。

三、总结

本题是将找到被X包围的O的问题,转化为找到所有在边界上的O,以及跟边界上的O相连的O的问题。

然后标记所有在边界的O以及跟边界的O相连的O,然后使用深度优先搜索算法,根据不同的情况进行替换即可。

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区),文章链接,文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:cloudbbs@huaweicloud.com进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。