最近以來,我在力扣上堅持完成每天一題,今天系統推的題目為《甲板上的戰艦》,在此記錄一下。 題目描述如下: 給你一個大小為 m x n 的矩陣 board 表示甲板,其中,每個單元格可以是一艘戰艦 'X' 或者是一個空位 '.' ,返回在甲板 board 上放置的 戰艦 的數量。 戰艦 只能水平或者垂 ...
最近以來,我在力扣上堅持完成每天一題,今天系統推的題目為《甲板上的戰艦》,在此記錄一下。
題目描述如下:
給你一個大小為 m x n 的矩陣 board 表示甲板,其中,每個單元格可以是一艘戰艦 'X' 或者是一個空位 '.' ,返回在甲板 board 上放置的 戰艦 的數量。
戰艦 只能水平或者垂直放置在 board 上。換句話說,戰艦隻能按 1 x k(1 行,k 列)或 k x 1(k 行,1 列)的形狀建造,其中 k 可以是任意大小。兩艘戰艦之間至少有一個水平或垂直的空位分隔 (即沒有相鄰的戰艦)。
示例 1:
輸入:board = [["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]]
輸出:2
示例 2:
輸入:board = [["."]]
輸出:0
拿到題目後,我的大致思路是這樣的:
1.定義一個count計數器,初始值為0
2.戰艦的擺放有哪些情況?經過思考後,我認為有以下三種情況:
<1>該戰艦為一個單獨的“點”,即只占數組中一個格子
<2>該戰艦為1×k類型的戰艦,即縱向戰艦,k>=2
<3>該戰艦為k×1類型的戰艦,即橫向戰艦,k>=2
3.什麼時候count增加?
對於一艘戰艦,我們遍曆數組時,只在戰艦的頭部(即首次在該艘戰艦上掃描到'X'時)將count+1,之後再次在該艘戰艦上掃描到'X'則不再增加
4.返回count值,程式結束
ok,思路有了,這道題已經做的十有八九了,接下來我們再來思考一個問題,即如何判斷我們掃描到的'X'是否是某艘戰艦的頭部呢?
當我們掃描到board[i][j]位置時,如果該位置為'X',並且該位置左側以及該位置上側不為'X',則該位置為某艘戰艦的頭部,此時count++
要註意的是,當i=0時,該位置是沒有上側的;當j=0時,該位置沒有左側。
代碼如下:
點擊查看代碼
public int countBattleships(char[][] board) {
int count = 0;
for(int i=0; i<board.length; i++){
for(int j=0; j<board[i].length; j++){
if(board[i][j] == 'X'){
if((i==0 || board[i-1][j]=='.')&& (j==0 || board[i][j-1]=='.'))
count++;
}
}
}
return count;
}