LeetCode 419 - Battleships in a Board

作者 QIFAN 日期 2017-06-07
LeetCode 419 - Battleships in a Board

原题链接: https://leetcode.com/problems/battleships-in-a-board/#/description


题干

在一个矩阵里放置战舰,用 N 个 X 代表战舰,. 代表空位。战舰只能横着放或者竖着放,且两艘战舰不能相邻。给定一个战舰排列矩阵,找出矩阵中战舰的数量。

例子:

X..X
...X
...X

2 艘战舰。

思路

本质是数有多少个 X 群,所以只需要数最开头的个数就可以了。最开头的定义就是左边或者上边没有 X

这个方法没有额外空间,时间复杂度是 $O(N^2)$

代码:

public int countBattleships(char[][] board) {
if (board == null || board.length == 0) {
return 0;
}
int count = 0;
for (int row = 0; row < board.length; row++) {
for (int col = 0; col < board[0].length; col++) {
if (board[row][col] == '.') {
continue;
}
if (row > 0 && board[row - 1][col] == 'X') {
continue;
}
if (col > 0 && board[row][col - 1] == 'X') {
continue;
}
count++;
}
}
return count;
}