网站备案公司,上海人才网官网登录,服务器网站建设教程视频,城市建设模拟游戏网站中文注解算法思想#xff08;解题思路#xff09;#xff1a;
这道题的核心是 将所有被边界包围的 O 保留下来#xff0c;而将其他被围绕的 O 转换为 X。为了实现这一目标#xff0c;我们可以分三步完成#xff1a; 第一步#xff1a;标记边界及其相连的 O 为特殊标记#xff…
算法思想解题思路
这道题的核心是 将所有被边界包围的 O 保留下来而将其他被围绕的 O 转换为 X。为了实现这一目标我们可以分三步完成 第一步标记边界及其相连的 O 为特殊标记例如 E 目标 找到所有与矩阵边界相连的 O将它们和与它们直接相连的所有 O 标记为一个特殊字符比如 E。这些 O 是不能被包围的因为它们直接或间接与边界相连。 方法 使用深度优先搜索DFS或广度优先搜索BFS从矩阵边界上的 O 开始向四个方向扩散将与边界相连的 O 都标记为 E。这样剩下的 O 就是被完全包围的。 第二步遍历整个矩阵处理不同状态的字符 目标 将矩阵中所有剩下的 O 转换为 X因为这些 O 是被完全包围的区域。将之前标记为 E 的字符还原为 O因为它们是不被包围的。 方法 遍历矩阵中的每一个元素根据字符值进行判断 如果是 O说明是被完全包围的区域改为 X。如果是 E说明是边界或与边界相连的 O改回 O。 第三步输出最终结果
经过上述处理矩阵会满足题目要求所有被包围的 O 转换为 X而没有被包围的 O 保留下来。 算法流程详解 初始化矩阵大小 首先判断输入矩阵是否为空。如果为空直接返回。 标记边界 遍历矩阵的 四个边界第一行、最后一行、第一列、最后一列。对边界上的每个 O用DFS递归标记其相连的 O 为 E。 遍历矩阵并修改字符 遍历矩阵中的所有元素 如果当前字符是 O说明它是被包围的转换为 X。如果当前字符是 E说明它是与边界相连的还原为 O。 时间与空间复杂度分析 时间复杂度O(m * n) 遍历矩阵的每个单元格一次并且在标记边界时每个单元格也最多访问一次。 空间复杂度 递归栈空间使用DFS时递归深度与矩阵的大小相关最坏情况下需要 O(m * n) 的栈空间。 示例说明
输入
board [[X, X, X, X],[X, O, O, X],[X, X, O, X],[X, O, X, X]
]执行过程 标记边界 第一步遍历边界发现 (3,1) 是 O并通过DFS标记与其相连的所有 O 为 E。标记后的矩阵[[X, X, X, X],[X, O, O, X],[X, X, O, X],[X, E, X, X]
]遍历矩阵修改字符 将所有未标记的 O 转换为 X。将标记为 E 的字符还原为 O。最终矩阵[[X, X, X, X],[X, X, X, X],[X, X, X, X],[X, O, X, X]
]输出
[[X, X, X, X],[X, X, X, X],[X, X, X, X],[X, O, X, X]
]总结
通过将与边界相连的 O 特殊标记我们可以有效区分哪些 O 是被围绕的最终实现题目要求。
class Solution {public void solve(char[][] board) {if(board null || board.length 0) return;//获取矩阵的行和列int rows board.length;int cols board[0].length;for(int i 0; i rows; i) {if(board[i][0] O) {dfs(board, i, 0);}if(board[i][cols - 1] O) {dfs(board, i, cols - 1);}}for(int j 0; j cols; j) {if(board[0][j] O) {dfs(board, 0, j);}if(board[rows - 1][j] O) {dfs(board, rows - 1, j);}}//然后将剩下的O转换为X, E 转换回 Ofor(int i 0; i rows; i) {for(int j 0; j cols; j) {if(board[i][j] O) {board[i][j] X;}if(board[i][j] E) {board[i][j] O;}}}}private void dfs(char[][] board, int row, int col) {//首先检查是否越界if(row 0 || row board.length || col 0 || col board[0].length || board[row][col] ! O) {return;}//将O标记为Eboard[row][col] E;dfs(board, row 1, col);dfs(board, row - 1, col);dfs(board, row, col 1);dfs(board, row, col - 1);}
}
