电商网站源代码,个人主页空间申请,免费苏州企业名录,上海网站建设服务公司【问题描述】[中等] 【解答思路】 1. 深度优先搜索
使用深度优先搜索实现标记操作。在下面的代码中#xff0c;我们把标记过的字母 O 修改为字母 A。 复杂度
class Solution {int[] dx {1, -1, 0, 0};int[] dy {0, 0, 1, -1};public void solve(char[][] board) {int n …【问题描述】[中等] 【解答思路】 1. 深度优先搜索
使用深度优先搜索实现标记操作。在下面的代码中我们把标记过的字母 O 修改为字母 A。 复杂度
class Solution {int[] dx {1, -1, 0, 0};int[] dy {0, 0, 1, -1};public void solve(char[][] board) {int n board.length;if (n 0) {return;}int m board[0].length;Queueint[] queue new LinkedListint[]();for (int i 0; i n; i) {if (board[i][0] O) {queue.offer(new int[]{i, 0});}if (board[i][m - 1] O) {queue.offer(new int[]{i, m - 1});}}for (int i 1; i m - 1; i) {if (board[0][i] O) {queue.offer(new int[]{0, i});}if (board[n - 1][i] O) {queue.offer(new int[]{n - 1, i});}}while (!queue.isEmpty()) {int[] cell queue.poll();int x cell[0], y cell[1];board[x][y] A;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;}queue.offer(new int[]{mx, 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;}}}}
}
2. 广度优先搜索
以使用广度优先搜索实现标记操作。在下面的代码中我们把标记过的字母 O 修改为字母 A 时间复杂度O(N) 空间复杂度O(1)
class Solution {int[] dx {1, -1, 0, 0};int[] dy {0, 0, 1, -1};public void solve(char[][] board) {int n board.length;if (n 0) {return;}int m board[0].length;Queueint[] queue new LinkedListint[]();for (int i 0; i n; i) {if (board[i][0] O) {queue.offer(new int[]{i, 0});}if (board[i][m - 1] O) {queue.offer(new int[]{i, m - 1});}}for (int i 1; i m - 1; i) {if (board[0][i] O) {queue.offer(new int[]{0, i});}if (board[n - 1][i] O) {queue.offer(new int[]{n - 1, i});}}while (!queue.isEmpty()) {int[] cell queue.poll();int x cell[0], y cell[1];board[x][y] A;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;}queue.offer(new int[]{mx, 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;}}}}
}
【总结】
1. 细节
1.1 方向定义 int[] dx {1, -1, 0, 0}; int[] dy {0, 0, 1, -1}; 1.2 边界判断 if (mx 0 || my 0 || mx n || my m || board[mx][my] ! ‘O’) { continue; }
著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。
2.DFS BFS 思路不复杂 注意细节 多写几遍
转载链接https://leetcode-cn.com/problems/surrounded-regions/solution/bei-wei-rao-de-qu-yu-by-leetcode-solution/
