419. Battleships in a Board

https://leetcode.com/problems/battleships-in-a-board/

给定一个N×N的棋盘,有任意数量的1×N或N×1大小的“船”,注意船船之间是不相邻的,要求统计有多少船

Example:

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

In the above board there are 2 battleships.

解题思路

Given an 2D board, count how many different battleships are in it.

这是题目头一句话,different这个词把我搞懵了,我的理解是如果在棋盘上如果有同样size,同样方向的船应该是算一种的

如["XX..","....","..XX"]这个例子,输出我觉得应该是1,但是我看了leetcode给的top solutions,按照这类解法,输出普遍是2

rucode了一下,结果如下:

Run Code Result:
Your input
["XX..","....","..XX"]
Expected answer
2
 
Runtime: 39 ms

说明其实只要统计棋盘里面有几条船就可以了

那么解法就很简单了,只用统计有多少个“船头”就可以了

船头定义如下:

1、是个X(废话)

2、上面为空(在棋盘边界)或为.

3、左边为空(在棋盘边界)或为.

同时注意测试用例其实是没有空棋盘(return0)的情况的,加上判空代码是处于严谨性

船头解法

 class Solution(object):#head,top_left
def countBattleships(self, board):
if len(board) == 0: return 0
m, n = len(board), len(board[0])
count = 0
for i in range(m):
for j in range(n):
if board[i][j] == 'X' and (i == 0 or board[i - 1][j] == '.') and (j == 0 or board[i][j - 1] == '.'):
count += 1
return count

按照同样的思路,你也可以统计船尾,左上改为右下即可

if board[i][j] == 'X' and (i == m-1 or board[i + 1][j] == '.') and (j == n-1 or board[i][j + 1] == '.')
上一篇:【bzoj1855】 [Scoi2010]股票交易 单调队列优化DP


下一篇:构造个人轻量级XSS平台获取管理员cookie并登录