题目描述
Given an 2D board, count how many battleships are in it. The battleships are represented with'X's, empty slots are represented with'.'s. You may assume the following rules:
You receive a valid board, made of only battleships or empty slots.
Battleships can only be placed horizontally or vertically. In other words, they can only be made of the shape1xN(1 row, N columns) orNx1(N rows, 1 column), where N can be of any size.
At least one horizontal or vertical cell separates between two battleships - there are no adjacent battleships.
Example:
X..X
...X
...X
In the above board there are 2 battleships.
Invalid Example:
...X
XXXX
...X
This is an invalid board that you will not receive - as battleships will always have a cell separating between them.
Follow up:
Could you do it inone-pass, using onlyO(1) extra memoryandwithout modifyingthe value of the board?
分析
本题比较简单，因为题目中限定了相邻战舰的情形不会存在，并且保证board中的战舰都是有效的，这样我们就不需要做有效性检查，直接数战舰就可以了。
问题：怎么样数？
策略：只要我们找到每个战舰的其实位置就可以知道总共有多少战舰。问题转化为怎么样寻找每个战舰的起始位置？ 很简单，我定义个搜索策略，即从上至下，从左至右进行战舰搜索，那么战舰的起始位置就被定义为以下三点：
- 位置(i,j)处的元素为'X'
- 位置(i,j)的左侧（如果左侧位置存在）位置(i - 1, j)是空位，即没有战舰存在
- 位置(i,j)的上侧（如果上侧位置存在）位置(i, j - 1)是空位，即没有战舰存在
满足以上三个条件，我们就认为搜索到了一个战舰的起始位置。
代码
class Solution(object):
def countBattleships(self, board):
"""
:type board: List[List[str]]
:rtype: int
"""
if not board:
return -1
m, n = len(board), len(board[0])
battleshipCount = 0
for i in range(m):
for j in range(n):
if board[i][j] == '.' or i > 0 and board[i - 1][j] == 'X' or j > 0 and board[i][j - 1] == 'X':
continue
battleshipCount += 1
return battleshipCount
代码截图
视频教程
中文讲解
http://v.youku.com/v_show/id_XMzEzNTk5MTU2NA==.html?spm=a2h1n.8251843.playList.5!2
https://www.youtube.com/watch?v=eiaFjipwkoc&feature=youtu.be
英文讲解
http://v.youku.com/v_show/id_XMzEzNjAxNDQ0NA==.html?f=51299950
https://www.youtube.com/watch?v=3e-y4Lnkkw8&feature=youtu.be
推荐Channel
Youtube Channel
https://www.youtube.com/channel/UCgOBOym0p20QGvsccsWHc0A
Youtube Channel
Youku 频道
http://i.youku.com/codingmonkey2017
Youku 频道
