给定一个 n*m 大小的的矩阵,矩阵中由 ‘X’ 和 ‘O’ 构成,找到所有被 ‘X’ 围绕的区域,并将其用 ‘X’ 填充。 例如: [[‘X’,’X’,’X’,’X’], [‘X’,’O’,’O’,’X’], [‘X’,’O’,’X’,’X’], [‘X’,’X’,’O’,’X’]] 中间的三个 ‘O’ 被 ‘X’围绕,因此将其填充为 ‘X’ ,但第四行的 ‘O’ 下方没有被 ‘X’ 围绕,因此不改变,结果为 [[‘X’,’X’,’X’,’X’], [‘X’,’X’,’X’,’X’], [‘X’,’X’,’X’,’X’], [‘X’,’X’,’O’,’X’]] 数据范围: ,矩阵中保证只含有 ‘X’ 和 ‘O’-笔试面试资料

这是qklbishe.com第19199 篇笔试面试资料
提供答案分析,通过本文《给定一个 n*m 大小的的矩阵,矩阵中由 ‘X’ 和 ‘O’ 构成,找到所有被 ‘X’ 围绕的区域,并将其用 ‘X’ 填充。
例如: [[‘X’,’X’,’X’,’X’], [‘X’,’O’,’O’,’X’], [‘X’,’O’,’X’,’X’], [‘X’,’X’,’O’,’X’]]
中间的三个 ‘O’ 被 ‘X’围绕,因此将其填充为 ‘X’ ,但第四行的 ‘O’ 下方没有被 ‘X’ 围绕,因此不改变,结果为 [[‘X’,’X’,’X’,’X’], [‘X’,’X’,’X’,’X’], [‘X’,’X’,’X’,’X’], [‘X’,’X’,’O’,’X’]]
数据范围: ,矩阵中保证只含有 ‘X’ 和 ‘O’-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:

给定一个 n*m 大小的的矩阵,矩阵中由 ‘X’ 和 ‘O’ 构成,找到所有被 ‘X’ 围绕的区域,并将其用 ‘X’ 填充。
例如:
[[‘X’,’X’,’X’,’X’],
[‘X’,’O’,’O’,’X’],
[‘X’,’O’,’X’,’X’],
[‘X’,’X’,’O’,’X’]]
中间的三个 ‘O’ 被 ‘X’围绕,因此将其填充为 ‘X’ ,但第四行的 ‘O’ 下方没有被 ‘X’ 围绕,因此不改变,结果为
[[‘X’,’X’,’X’,’X’],
[‘X’,’X’,’X’,’X’],
[‘X’,’X’,’X’,’X’],
[‘X’,’X’,’O’,’X’]]

数据范围: 给定一个 n*m 大小的的矩阵,矩阵中由 ‘X' 和 'O' 构成,找到所有被 'X' 围绕的区域,并将其用 'X' 填充。          例如:    [['X','X','X','X'],    ['X','O','O','X'],    ['X','O','X','X'],    ['X','X','O','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’
Java

给定一个 n*m 大小的的矩阵,矩阵中由 ‘X' 和 'O' 构成,找到所有被 'X' 围绕的区域,并将其用 'X' 填充。          例如:    [['X','X','X','X'],    ['X','O','O','X'],    ['X','O','X','X'],    ['X','X','O','X']]      中间的三个 ‘O’ 被 'X'围绕,因此将其填充为 'X' ,但第四行的 'O' 下方没有被 'X' 围绕,因此不改变,结果为       [['X','X','X','X'],       ['X','X','X','X'],       ['X','X','X','X'],       ['X','X','O','X']]         数据范围:  ,矩阵中保证只含有 'X' 和 'O' 零葬

算法流程

思路很简单,直接用DFS求解
  1. 先遍历整个矩阵的边界,发现边界有O就开始进行深搜,把边界O连通的趋于全部LOCK住(将O改为L)。此时矩阵中剩下的O就是被X所围绕的封闭区域。
  2. 然后双重循环,把矩阵中剩下的O改成X。
  3. 最后把步骤1中锁住的O还原。
import java.util.*;   public class Solution {     /**      * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可      *      *       * @param board char字符型二维数组       * @return char字符型二维数组      */     int[] dx = new int[]{-1, 1, 0, 0};     int[] dy = new int[]{0, 0, -1, 1};     public char[][] surroundedArea (char[][] board) {         // 溜边界,先把边界处的O找到,然后锁死它的连通区域         int n = board.length, m = board[0].length;         for(int j = 0; j < board[0].length; j++){             if(board[0][j] == 'O'){                 dfs(board, 0, j);             }             if(board[n - 1][j] == 'O'){                 dfs(board, n - 1, j);             }         }         for(int i = 1; i < n - 1; i++){             if(board[i][0] == 'O'){                 dfs(board, i, 0);             }             if(board[i][m - 1] == 'O'){                 dfs(board, i, m - 1);             }         }         // 其他的O就是被围绕的O,将其充填为X         for(int i = 1; i < n - 1; i++){             for(int j = 1; j < m - 1; j++){                 if(board[i][j] == 'O'){                     board[i][j] = 'X';                 }             }         }         // 把之前锁死的O改回来         for(int i = 0; i < n; i++){             for(int j = 0; j < m; j++){                 if(board[i][j] == 'L'){                     board[i][j] = 'O';                 }             }         }         return board;     }          private void dfs(char[][] board, int x, int y) {         if(x < 0 || x >= board.length || y < 0 || y >= board[0].length || board[x][y] != 'O'){             return;     // 越界或已经不是O就直接返回         }         board[x][y] = 'L';    // LOCKED锁住         for(int i = 0; i < 4; i++){             dfs(board, x + dx[i], y + dy[i]);         }     } } 

复杂度分析

时间复杂度

  1. DFS:对于某个位置(i,j),逻辑上它会被自己的上下左右调用4次,而实际上只要有一次把O改成L后就再也不会在此处递归展开了(最少调用一次,最多调用4次)。因此某个位置只会有限几次被深搜,该步骤的时间复杂度为O(nm)。
  2. 矩阵遍历:双重循环遍历,时间复杂度为O(nm)。

综合以上两个步骤,算法的整体时间复杂度为O(nm)。

空间复杂度

直接在原始矩阵上进行的修改,因此额外空间复杂度O(1)。

2021-12-19 18:21:43 回复(0)

文章部分来自互联网,侵权联系删除
www.qklbishe.com

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 给定一个 n*m 大小的的矩阵,矩阵中由 ‘X’ 和 ‘O’ 构成,找到所有被 ‘X’ 围绕的区域,并将其用 ‘X’ 填充。 例如: [[‘X’,’X’,’X’,’X’], [‘X’,’O’,’O’,’X’], [‘X’,’O’,’X’,’X’], [‘X’,’X’,’O’,’X’]] 中间的三个 ‘O’ 被 ‘X’围绕,因此将其填充为 ‘X’ ,但第四行的 ‘O’ 下方没有被 ‘X’ 围绕,因此不改变,结果为 [[‘X’,’X’,’X’,’X’], [‘X’,’X’,’X’,’X’], [‘X’,’X’,’X’,’X’], [‘X’,’X’,’O’,’X’]] 数据范围: ,矩阵中保证只含有 ‘X’ 和 ‘O’-笔试面试资料

提供最优质的资源集合

立即查看 了解详情