本文共 1872 字,大约阅读时间需要 6 分钟。
给定一个二维字符数组board,board中每个字符都是'X'或者'O'。现在要求将所有被'X'包围'O'变为'X'。规定:在边界上的'O'默认不被'X'包围。例子:
图的DFS。
class Solution { public void solve(char[][] board) { if (board.length <= 1) return ; // 使用dfs将边界以及与其相连接的'O'变为'#' for (int j = 0; j < board[0].length; j++) { // 第一行 if (board[0][j] == 'O') dfs(board, 0, j); // 最后一行 if (board[board.length - 1][j] == 'O') dfs(board, board.length - 1, j); } for (int i = 0; i < board.length; i++) { // 第一列 if (board[i][0] == 'O') dfs(board, i, 0); // 最后一列 if (board[i][board[0].length - 1] == 'O') dfs(board, i, board[0].length - 1); } // 将board中所有的'O'变为'X' for (int i = 0; i < board.length; i++) { for (int j = 0; j < board[0].length; j++) { if (board[i][j] == 'O') board[i][j] = 'X'; } } // 将board中所有的'#'变为'O' for (int i = 0; i < board.length; i++) { for (int j = 0; j < board[0].length; j++) { if (board[i][j] == '#') board[i][j] = 'O'; } } } public void dfs(char[][] board, int r, int c) { board[r][c] = '#'; if (r - 1 >= 0 && board[r - 1][c] == 'O') dfs(board, r - 1, c); if (r + 1 < board.length && board[r + 1][c] == 'O') dfs(board, r + 1, c); if (c - 1 >= 0 && board[r][c - 1] == 'O') dfs(board, r, c - 1); if (c + 1 < board[0].length && board[r][c + 1] == 'O') dfs(board, r, c + 1); }}
对board进行了3次遍历,但是时间效率还是很高的。但为什么这个空间效率这么低???
转载地址:http://dxesi.baihongyu.com/