Leetcode419 甲板上的战舰

cnblogs 2024-06-11 13:39:00 阅读 78

最近以来,我在力扣上坚持完成每天一题,今天系统推的题目为《甲板上的战舰》,在此记录一下。

题目描述如下:

给你一个大小为 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;

}


上一篇: C++初阶 内存管理和模板

下一篇: python 爬虫 m3u8 视频文件 加密解密 整合mp4

本文标签

战舰    题目    'X'    count    board   


声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。