leetcode做题笔记130. 被围绕的区域

这篇具有很好参考价值的文章主要介绍了leetcode做题笔记130. 被围绕的区域。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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

思路一:深度优先(DFS)

const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};

void solve(char** board, int boardSize, int* boardColSize) {
    int n = boardSize;
    if (n == 0) {
        return;
    }
    int m = boardColSize[0];

    int** que = (int**)malloc(sizeof(int*) * n * m);
    for (int i = 0; i < n * m; i++) {
        que[i] = (int*)malloc(sizeof(int) * 2);
    }
    int l = 0, r = 0;
    for (int i = 0; i < n; i++) {
        if (board[i][0] == 'O') {
            board[i][0] = 'A';
            que[r][0] = i, que[r++][1] = 0;
        }
        if (board[i][m - 1] == 'O') {
            board[i][m - 1] = 'A';
            que[r][0] = i, que[r++][1] = m - 1;
        }
    }
    for (int i = 1; i < m - 1; i++) {
        if (board[0][i] == 'O') {
            board[0][i] = 'A';
            que[r][0] = 0, que[r++][1] = i;
        }
        if (board[n - 1][i] == 'O') {
            board[n - 1][i] = 'A';
            que[r][0] = n - 1, que[r++][1] = i;
        }
    }
    while (l < r) {
        int x = que[l][0], y = que[l][1];
        l++;
        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;
            }
            board[mx][my] = 'A';
            que[r][0] = mx, que[r++][1] = 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';
            }
        }
    }
    for (int i = 0; i < n * m; i++) {
        free(que[i]);
    }
    free(que);
}

分析:

本题若从内向外分析则难以判断是否需要将O替换为X,所以从外向内分析。从外向内分析时可考虑将最外层的O先替换为A,再判断内部O是否与A相邻,并设置方向数组方便判断方向,最后从外向内递归数组即可完成

总结:

本题考察对深度优先搜索的应用,分析出从外向内不断判断的方法,再将边界情况考虑清楚即可解决文章来源地址https://www.toymoban.com/news/detail-701145.html

到了这里,关于leetcode做题笔记130. 被围绕的区域的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 代码随想录| 图论02●695岛屿最大面积 ●1020飞地的数量 ●130被围绕的区域 ●417太平洋大西洋水流问题

    #695岛屿最大面积 模板题,很快.以下两种dfs,区别是看第一个点放不放到dfs函数中处理,那么初始化的area一个是1一个是0  bfs:对应也有两种 #1020飞地的数量 下面是自己写的dfs,过了但是很多可以改进。bfs也差不多这里就不写了  可改进的点: 1 其实遍历四周可以四个循环合

    2024年02月16日
    浏览(47)
  • FloodFill算法——力扣被围绕的区域

    被围绕的区域 我们来解读一下这个题目,这个题目的意思就是求出被X围绕的O有多少个,那么什么是被围绕呢?也就是没有出路并且连通的O不能到四条边上,这就算是被围绕了,可是即使知道了这些信息我们依旧头大因为,太难分析了我们遇到一个O之后还得去看看这一块儿

    2024年03月25日
    浏览(40)
  • leetcode做题笔记58

    给你一个字符串  s ,由若干单词组成,单词前后用一些空格字符隔开。返回字符串中  最后一个  单词的长度。 单词  是指仅由字母组成、不包含任何空格字符的最大子字符串。 本题要求最后一个单词长度,只需从后向前遍历,ans不断增加,一旦遇到空格则输出ans的值 本

    2024年02月14日
    浏览(44)
  • leetcode做题笔记45

    给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i + j] 处: 0 = j = nums[i]  i + j n 返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

    2024年02月15日
    浏览(55)
  • leetcode做题笔记41

    给你一个未排序的整数数组  nums  ,请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为  O(n)  并且只使用常数级别额外空间的解决方案。 目录 思路一:利用负数进行区分 分析: 思路二:交换法 分析: 总结: 时间复杂度O(n),空间复杂度O(1) 本题一开始想到

    2024年02月16日
    浏览(36)
  • leetcode做题笔记43

     给定两个以字符串形式表示的非负整数 num1 和 num2,返回 num1 和 num2 的乘积,它们的乘积也表示为字符串形式。 注意:不能使用任何内置的 BigInteger 库或直接将输入转换为整数。 目录 思路一: 分析: 总结: 时间复杂度O(n*m),空间复杂度O(n) 本题一开始先将两个字符串

    2024年02月15日
    浏览(33)
  • leetcode做题笔记53

    给你一个整数数组  nums  ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 子数组  是数组中的一个连续部分。 时间复杂度O(n),空间复杂度O(1) 本题要求最大子数组和,可考虑先求出每个元素的前缀和,再判断是否前缀和加现元素是否

    2024年02月14日
    浏览(59)
  • leetcode做题笔记59

    给你一个正整数  n  ,生成一个包含  1  到  n2  所有元素,且元素按顺时针顺序螺旋排列的  n x n  正方形矩阵  matrix  。 时间复杂度O(n),空间复杂度O(n^2) 本题要按顺时针顺序排列数组后输出,可设置对应的方向数组,将递增的数通过方向数组放置到正确的位置,最后输

    2024年02月14日
    浏览(39)
  • leetcode做题笔记72

    给你两个单词  word1  和  word2 ,  请返回将  word1  转换成  word2  所使用的最少操作数   。 你可以对一个单词进行如下三种操作: 插入一个字符 删除一个字符 替换一个字符 时间复杂度O(n^2),空间复杂度O(n) 本题将一个字符串变为另一个字符串,首先长度需变为一致,即

    2024年02月13日
    浏览(40)
  • leetcode做题笔记69

    给你一个非负整数  x  ,计算并返回  x  的  算术平方根  。 由于返回类型是整数,结果只保留  整数部分  ,小数部分将被  舍去 。 注意: 不允许使用任何内置指数函数和算符,例如  pow(x, 0.5)  或者  x ** 0.5  。 由于本题是求平方根,可直接看中位数的平方是否大于

    2024年02月13日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包