赞
踩
目录
给你一个大小为 m x n 的矩阵 board 表示甲板,其中,每个单元格可以是一艘战舰 'X' 或者是一个空位 '.' ,返回在甲板 board 上放置的 战舰 的数量。
战舰 只能水平或者垂直放置在 board 上。换句话说,战舰只能按 1 x k(1 行,k 列)或 k x 1(k 行,1 列)的形状建造,其中 k 可以是任意大小。两艘战舰之间至少有一个水平或垂直的空位分隔 (即没有相邻的战舰)。
意思就是一个x行和列 ,仅仅统计一次
普通解法,在遍历到一个'X'时,DFS以下与其连接的'X';
修改原数组为其他字符;
统计最后个数。
- class Solution:
- def countBattleships(self, board):
- cnt = 0
- for i in range(len(board)):
- for j in range(len(board[0])):
- if board[i][j] == 'X':
- board[i][j] = 'Y'
- m,n = i,j
- while n + 1 < len(board[0]) and board[m][n + 1] == 'X':
- board[m][n + 1] = 'Y'
- n += 1
- while m + 1 < len(board) and board[m + 1][n] == 'X':
- board[m + 1][n] = 'Y'
- m += 1
- cnt += 1
- return cnt
-
for i in range(len(board)):
for j in range(len(board[0])):遍历整个数组
我们可以通过战舰的头来判断个数,当一个点上面或者左面试
X
说明它战舰中间部分,跳过即可!
- class Solution:
- def countBattleships(self, board: List[List[str]]) -> int:
- row = len(board)
- col = len(board[0])
- res = 0
- for i in range(row):
- for j in range(col):
- if board[i][j] == ".": continue
- if i > 0 and board[i - 1][j] == "X": continue
- if j > 0 and board[i][j - 1] == "X": continue
- res += 1
- return res
1) if board[i][j] == ".": continue 意思是如果board[i][j] == "."
继续 for j in range(col):
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。