搜索题目：甲板上的战舰

文章目录题目标题和出处难度题目描述要求示例数据范围进阶解法一思路和算法代码复杂度分析解法二思路和算法代码复杂度分析解法三预备知识思路和算法代码复杂度分析解法四思路和算法代码复杂度分析题目标题和出处标题甲板上的战舰出处419. 甲板上的战舰难度4 级题目描述要求给定一个m × n \texttt{m} \times \texttt{n}m×n的矩阵board \texttt{board}board表示甲板其中每个单元格可以是战舰‘X’ \texttt{X}‘X’或者是空位‘.’ \texttt{.}‘.’返回在board \texttt{board}board上放置的战舰的数量。战舰只能水平或者竖直放置在board \texttt{board}board上。换句话说战舰只能按1 × k \texttt{1} \times \texttt{k}1×k1 \texttt{1}1行k \texttt{k}k列或k × 1 \texttt{k} \times \texttt{1}k×1k \texttt{k}k行1 \texttt{1}1列的形状建造其中k \texttt{k}k可以是任意大小。两艘战舰之间至少有一个水平或竖直的空位分隔即没有相邻的战舰。示例示例 1输入board [[X,.,.,X],[.,.,.,X],[.,.,.,X]] \texttt{board [[X,.,.,X],[.,.,.,X],[.,.,.,X]]}board [[X,.,.,X],[.,.,.,X],[.,.,.,X]]输出2 \texttt{2}2示例 2输入board [[.]] \texttt{board [[.]]}board [[.]]输出0 \texttt{0}0数据范围m board.length \texttt{m} \texttt{board.length}mboard.lengthn board[i].length \texttt{n} \texttt{board[i].length}nboard[i].length1 ≤ m, n ≤ 200 \texttt{1} \le \texttt{m, n} \le \texttt{200}1≤m, n≤200board[i][j] \texttt{board[i][j]}board[i][j]是‘.’ \texttt{.}‘.’或‘X’ \texttt{X}‘X’进阶你是否可以遍历一次只使用O(1) \texttt{O(1)}O(1)额外空间且不修改board \texttt{board}board的值来解决这个问题解法一思路和算法由于同一个战舰在矩阵中占据的元素相邻且不同战舰之间不相邻因此可以使用广度优先搜索计算战舰数量。以下将‘X’ \text{X}‘X’称为「战舰元素」。广度优先搜索需要使用与矩阵相同大小的二维数组记录每个元素是否被访问过初始时所有元素的状态都是未访问。依次遍历矩阵中的每个元素如果遇到一个元素是战舰元素且状态是未访问则遇到一个新的战舰将战舰数量加1 11并访问与当前战舰元素连接的所有战舰元素即访问当前战舰的所有元素。遍历结束之后即可得到战舰数量。实现方面有以下两点说明。从一个战舰元素开始遍历整个战舰时对于每个战舰元素考虑与当前战舰元素在四个方向上相邻且未访问的战舰元素可以创建方向数组实现四个方向的遍历。此处的解法为新建与矩阵相同大小的二维数组记录每个元素是否被访问过也可以不新建二维数组而是在矩阵上原地修改访问过的元素。虽然原地修改可以省略新建二维数组的空间但是不能省略队列空间因此空间复杂度相同而且原地修改会改变矩阵的元素使得计算战舰数量之后无法再次使用矩阵信息。代码classSolution{staticint[][]dirs{{-1,0},{1,0},{0,-1},{0,1}};publicintcountBattleships(char[][]board){intbattleships0;intmboard.length,nboard[0].length;boolean[][]visitednewboolean[m][n];for(inti0;im;i){for(intj0;jn;j){if(board[i][j].||visited[i][j]){continue;}battleships;visited[i][j]true;Queueint[]queuenewArrayDequeint[]();queue.offer(newint[]{i,j});while(!queue.isEmpty()){int[]cellqueue.poll();introwcell[0],colcell[1];for(int[]dir:dirs){intnewRowrowdir[0],newColcoldir[1];if(newRow0newRowmnewCol0newColnboard[newRow][newCol]X!visited[newRow][newCol]){visited[newRow][newCol]true;queue.offer(newint[]{newRow,newCol});}}}}}returnbattleships;}}复杂度分析时间复杂度O ( m n ) O(mn)O(mn)其中m mm和n nn分别是矩阵board \textit{board}board的行数和列数。广度优先搜索最多需要访问每个元素一次。空间复杂度O ( m n ) O(mn)O(mn)其中m mm和n nn分别是矩阵board \textit{board}board的行数和列数。记录每个元素是否被访问过的二维数组和队列需要O ( m n ) O(mn)O(mn)的空间。解法二思路和算法也可以使用深度优先搜索计算战舰数量。深度优先搜索需要使用与矩阵相同大小的二维数组记录每个元素是否被访问过初始时所有元素的状态都是未访问。依次遍历矩阵中的每个元素如果遇到一个元素是战舰元素且状态是未访问则遇到一个新的战舰将战舰数量加1 11并访问与当前战舰元素连接的所有战舰元素即访问当前战舰的所有元素。遍历结束之后即可得到战舰数量。实现方面有以下两点说明。从一个战舰元素开始遍历整个战舰时对于每个战舰元素考虑与当前战舰元素在四个方向上相邻且未访问的战舰元素可以创建方向数组实现四个方向的遍历。此处的解法为新建与矩阵相同大小的二维数组记录每个元素是否被访问过也可以不新建二维数组而是在矩阵上原地修改访问过的元素。虽然原地修改可以省略新建二维数组的空间但是不能省略递归调用栈空间因此空间复杂度相同而且原地修改会改变矩阵的元素使得计算战舰数量之后无法再次使用矩阵信息。代码classSolution{staticint[][]dirs{{-1,0},{1,0},{0,-1},{0,1}};intm,n;char[][]board;boolean[][]visited;publicintcountBattleships(char[][]board){intbattleships0;this.mboard.length;this.nboard[0].length;this.boardboard;this.visitednewboolean[m][n];for(inti0;im;i){for(intj0;jn;j){if(board[i][j].||visited[i][j]){continue;}battleships;dfs(i,j);}}returnbattleships;}publicvoiddfs(introw,intcol){visited[row][col]true;for(int[]dir:dirs){intnewRowrowdir[0],newColcoldir[1];if(newRow0newRowmnewCol0newColnboard[newRow][newCol]X!visited[newRow][newCol]){dfs(newRow,newCol);}}}}复杂度分析时间复杂度O ( m n ) O(mn)O(mn)其中m mm和n nn分别是矩阵board \textit{board}board的行数和列数。深度优先搜索最多需要访问每个元素一次。空间复杂度O ( m n ) O(mn)O(mn)其中m mm和n nn分别是矩阵board \textit{board}board的行数和列数。记录每个元素是否被访问过的二维数组和递归调用栈需要O ( m n ) O(mn)O(mn)的空间。解法三预备知识该解法涉及到并查集。并查集是一种树型的数据结构用于处理不相交集合的合并与查询问题。思路和算法由于战舰由相邻的战舰元素连接形成因此战舰数量为战舰元素组成的连通分量数连通性问题可以使用并查集解决。并查集初始化时每个战舰元素元素分别属于不同的集合每个集合只包含一个战舰元素元素集合个数等于战舰元素元素个数。初始化之后遍历每个元素如果一个元素是战舰元素元素且其上边或左边的相邻元素是战舰元素元素则将两个相邻战舰元素元素所在的集合做合并每次合并之后将集合个数减1 11。遍历结束之后并查集的集合个数即为战舰数量。代码classSolution{publicintcountBattleships(char[][]board){intmboard.length,nboard[0].length;intxCounts0;for(inti0;im;i){for(intj0;jn;j){if(board[i][j]X){xCounts;}}}UnionFindufnewUnionFind(m*n,xCounts);for(inti0;im;i){for(intj0;jn;j){if(board[i][j]X){if(i0board[i-1][j]X){uf.union(i*nj,(i-1)*nj);}if(j0board[i][j-1]X){uf.union(i*nj,i*nj-1);}}}}returnuf.getCount();}}classUnionFind{privateint[]parent;privateint[]rank;privateintcount;publicUnionFind(intn,intcount){parentnewint[n];for(inti0;in;i){parent[i]i;}ranknewint[n];this.countcount;}publicvoidunion(intx,inty){introotxfind(x);introotyfind(y);if(rootx!rooty){if(rank[rootx]rank[rooty]){parent[rooty]rootx;}elseif(rank[rootx]rank[rooty]){parent[rootx]rooty;}else{parent[rooty]rootx;rank[rootx];}count--;}}publicintfind(intx){if(parent[x]!x){parent[x]find(parent[x]);}returnparent[x];}publicintgetCount(){returncount;}}复杂度分析时间复杂度O ( m n × α ( m n ) ) O(mn \times \alpha(mn))O(mn×α(mn))其中m mm和n nn分别是矩阵board \textit{board}board的行数和列数α \alphaα是反阿克曼函数。并查集的初始化需要O ( m n ) O(mn)O(mn)的时间然后遍历m n mnmn个元素执行O ( m n ) O(mn)O(mn)次合并操作这里的并查集使用了路径压缩和按秩合并单次操作的时间复杂度是O ( α ( m n ) ) O(\alpha(mn))O(α(mn))因此并查集初始化之后的操作的时间复杂度是O ( m n × α ( m n ) ) O(mn \times \alpha(mn))O(mn×α(mn))总时间复杂度是O ( m n m n × α ( m n ) ) O ( m n × α ( m n ) ) O(mn mn \times \alpha(mn)) O(mn \times \alpha(mn))O(mnmn×α(mn))O(mn×α(mn))。空间复杂度O ( m n ) O(mn)O(mn)其中m mm和n nn分别是矩阵board \textit{board}board的行数和列数。并查集需要O ( m n ) O(mn)O(mn)的空间。解法四思路和算法由于每个战舰都是1 11行k kk列或k kk行1 11列且不同战舰之间不相邻因此每个战舰都有一个左上角元素左上角元素满足该元素是战舰元素且该元素的上边和左边的相邻元素都是空位这里假设board \textit{board}board的四条边均被空位包围。可以遍历矩阵一次通过寻找每个战舰的左上角元素的做法计算战舰数量该做法的空间复杂度是O ( 1 ) O(1)O(1)且不修改board \textit{board}board的值。遍历矩阵board \textit{board}board对于每个战舰元素board [ i ] [ j ] \textit{board}[i][j]board[i][j]判断该元素是否为左上角元素如果i 0 i 0i0或board [ i − 1 ] [ j ] \textit{board}[i - 1][j]board[i−1][j]不是战舰元素且j 0 j 0j0或board [ i ] [ j − 1 ] \textit{board}[i][j - 1]board[i][j−1]不是战舰元素则board [ i ] [ j ] \textit{board}[i][j]board[i][j]是左上角元素。每次遇到左上角元素则将战舰数量加1 11遍历结束之后即可得到战舰数量。代码classSolution{publicintcountBattleships(char[][]board){intbattleships0;intmboard.length,nboard[0].length;for(inti0;im;i){for(intj0;jn;j){if(isTopLeftCorner(board,i,j)){battleships;}}}returnbattleships;}publicbooleanisTopLeftCorner(char[][]board,introw,intcol){returnboard[row][col]X(row0||board[row-1][col]!X)(col0||board[row][col-1]!X);}}复杂度分析时间复杂度O ( m n ) O(mn)O(mn)其中m mm和n nn分别是矩阵board \textit{board}board的行数和列数。需要访问每个元素一次。空间复杂度O ( 1 ) O(1)O(1)。