LeetCode题练习与总结:被围绕的区域--130

2024-06-18 16:44

本文主要是介绍LeetCode题练习与总结:被围绕的区域--130,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一、题目描述

给你一个 m x n 的矩阵 board ,由若干字符 'X' 和 'O' 组成,捕获 所有 被围绕的区域

  • 连接:一个单元格与水平或垂直方向上相邻的单元格连接。
  • 区域:连接所有 '0' 的单元格来形成一个区域。
  • 围绕:如果您可以用 'X' 单元格 连接这个区域,并且区域中没有任何单元格位于 board 边缘,则该区域被 'X' 单元格围绕。

示例 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"]]

解释:

在上图中,底部的区域没有被捕获,因为它在 board 的边缘并且不能被围绕。

示例 2:

输入:board = [["X"]]

输出:[["X"]]

提示:

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 200
  • board[i][j] 为 'X' 或 'O'

二、解题思路

这个问题是典型的深度优先搜索(DFS)或并查集(Union-Find)问题。我们可以用DFS来解决这个问题,思路是:

  1. 寻找边界上的’O’:首先,我们需要遍历矩阵的边界,找到所有边界上的’O’。
  2. 深度优先搜索:从这些边界上的’O’开始,使用DFS将所有与之相连的’O’标记为另一个特殊字符,例如’#‘,表示这些’O’不应被替换为’X’。
  3. 替换剩余的’O’:再次遍历整个矩阵,将未被标记为’#‘的’O’替换为’X’。
  4. 还原特殊字符:最后,再次遍历矩阵,将所有的’#‘还原为’O’。

三、具体代码

class Solution {private int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};private int m, n;public void solve(char[][] board) {if (board == null || board.length == 0) return;m = board.length;n = board[0].length;// Step 1: Find 'O' on the border and start DFSfor (int i = 0; i < m; i++) {dfs(board, i, 0);      // Left borderdfs(board, i, n - 1);  // Right border}for (int j = 0; j < n; j++) {dfs(board, 0, j);      // Top borderdfs(board, m - 1, j);  // Bottom border}// Step 2: Replace 'O' with 'X'for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (board[i][j] == 'O') {board[i][j] = 'X';}}}// Step 3: Restore '#' to 'O'for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (board[i][j] == '#') {board[i][j] = 'O';}}}}private void dfs(char[][] board, int i, int j) {if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O') {return;}board[i][j] = '#';for (int[] dir : directions) {dfs(board, i + dir[0], j + dir[1]);}}
}

四、时间复杂度和空间复杂度

1. 时间复杂度
  • 遍历矩阵的边界以寻找’O’并开始DFS的过程,这一步的时间复杂度是O(m+n),因为矩阵的边界上的单元格总数是m+n。
  • 对每个找到的’O’执行DFS,这一步的时间复杂度是O(m*n),因为在最坏的情况下,整个矩阵都可能被遍历。
  • 再次遍历矩阵以替换’O’为’X’,这一步的时间复杂度是O(m*n)。
  • 最后,再次遍历矩阵以还原’#‘为’O’,这一步的时间复杂度也是O(m*n)。
  • 综上所述,总的时间复杂度是O(mn),因为虽然第一步是O(m+n),但是它相比于后面的O(mn)可以忽略不计。
2. 空间复杂度
  • DFS的递归调用会使用栈空间,最坏情况下整个矩阵都是’O’,递归的深度将达到mn,因此空间复杂度是O(mn)。

综上所述,代码的时间复杂度是O(mn),空间复杂度也是O(mn)。

五、总结知识点

  1. 二维数组的遍历:代码中多次使用了两层嵌套的for循环来遍历二维数组,这是处理二维数据结构的基本操作。

  2. 深度优先搜索(DFS)dfs函数实现了深度优先搜索算法,这是一种用于遍历或搜索树或图的算法。在这个问题中,DFS用于找到并标记所有与边界上的’O’相连的’O’。

  3. 递归dfs函数是递归的,它自己调用来遍历所有相邻的’O’。递归是一种常用的算法技巧,用于将复杂问题分解为更小的相似问题。

  4. 辅助空间的使用:代码中使用了一个二维数组directions来存储四个方向上的移动向量,这有助于在DFS中简化代码。

  5. 边界条件检查:在dfs函数中,代码首先检查当前坐标是否越界或者是否是’O’,这是递归的基本安全和正确性保证。

  6. 原地修改:代码直接在输入的board数组上进行修改,而不是创建新的数组,这是一种节省空间的做法。

  7. 特殊标记和状态转换:代码中使用特殊字符’#‘来标记那些不应该被替换为’X’的’O’,这是一种常见的编程技巧,用于在算法执行过程中保持临时状态。

  8. 模拟:整个算法模拟了从一个状态转换到另一个状态的过程,首先标记所有不应该被捕获的区域,然后进行捕获操作,最后恢复标记的区域。

以上就是解决这个问题的详细步骤,希望能够为各位提供启发和帮助。

这篇关于LeetCode题练习与总结:被围绕的区域--130的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1072548

相关文章

HarmonyOS学习(七)——UI(五)常用布局总结

自适应布局 1.1、线性布局(LinearLayout) 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列,Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距,达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式,且在各类尺寸屏幕上表现一致,其中交叉轴为垂直时,取值为Vert

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

学习hash总结

2014/1/29/   最近刚开始学hash,名字很陌生,但是hash的思想却很熟悉,以前早就做过此类的题,但是不知道这就是hash思想而已,说白了hash就是一个映射,往往灵活利用数组的下标来实现算法,hash的作用:1、判重;2、统计次数;

git使用的说明总结

Git使用说明 下载安装(下载地址) macOS: Git - Downloading macOS Windows: Git - Downloading Windows Linux/Unix: Git (git-scm.com) 创建新仓库 本地创建新仓库:创建新文件夹,进入文件夹目录,执行指令 git init ,用以创建新的git 克隆仓库 执行指令用以创建一个本地仓库的

二分最大匹配总结

HDU 2444  黑白染色 ,二分图判定 const int maxn = 208 ;vector<int> g[maxn] ;int n ;bool vis[maxn] ;int match[maxn] ;;int color[maxn] ;int setcolor(int u , int c){color[u] = c ;for(vector<int>::iter

整数Hash散列总结

方法:    step1  :线性探测  step2 散列   当 h(k)位置已经存储有元素的时候,依次探查(h(k)+i) mod S, i=1,2,3…,直到找到空的存储单元为止。其中,S为 数组长度。 HDU 1496   a*x1^2+b*x2^2+c*x3^2+d*x4^2=0 。 x在 [-100,100] 解的个数  const int MaxN = 3000

状态dp总结

zoj 3631  N 个数中选若干数和(只能选一次)<=M 的最大值 const int Max_N = 38 ;int a[1<<16] , b[1<<16] , x[Max_N] , e[Max_N] ;void GetNum(int g[] , int n , int s[] , int &m){ int i , j , t ;m = 0 ;for(i = 0 ;

RabbitMQ练习(AMQP 0-9-1 Overview)

1、What is AMQP 0-9-1 AMQP 0-9-1(高级消息队列协议)是一种网络协议,它允许遵从该协议的客户端(Publisher或者Consumer)应用程序与遵从该协议的消息中间件代理(Broker,如RabbitMQ)进行通信。 AMQP 0-9-1模型的核心概念包括消息发布者(producers/publisher)、消息(messages)、交换机(exchanges)、

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists