LeetCode刷题实战419：甲板上的战舰

Love The Way You Lie 2022-09-17 03:08 156阅读 0赞

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！

今天和大家聊的问题叫做 **甲板上的战舰**，我们先来看题面：

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

Given an m x n matrix board where each cell is a battleship 'X' or empty '.', return the number of the battleships on board.

Battleships can only be placed horizontally or vertically on board. In other words, they can only be made of the shape 1 x k (1 row, k columns) or k x 1 (k rows, 1 column), where k can be of any size. At least one horizontal or vertical cell separates between two battleships (i.e., there are no adjacent battleships).

给定一个二维的甲板， 请计算其中有多少艘战舰。战舰用 'X'表示，空位用 '.'表示。你需要遵守以下规则：

给你一个有效的甲板，仅由战舰或者空位组成。

战舰只能水平或者垂直放置。换句话说,战舰只能由 1xN (1 行, N 列)组成，或者 Nx1 (N 行, 1 列)组成，其中N可以是任意大小。

两艘战舰之间至少有一个水平或垂直的空位分隔 - 即没有相邻的战舰。

## **示例** ##

![76cbb20d49a68ba3748f5dbcffa6394d.png][]

## **解题** ##

解题思路：

按顺序放时，从左到右 ，从上到下，所以只需要考虑，上，左有无空位即可

class Solution:
        def countBattleships(self, board: List[List[str]]) -> int:
            count = 0
            for i in range(len(board)):
                for j in range(len(board[0])):
                    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

好了，今天的文章就到这里，如果觉得有所收获，请顺手点个**在看**或者转发吧，你们的支持是我最大的动力 。

**上期推文：**

[LeetCode1-400题汇总，希望对你有点帮助！][LeetCode1-400]

[LeetCode刷题实战401：二进制手表][LeetCode_401]

[LeetCode刷题实战402：移掉 K 位数字][LeetCode_402_ K]

[LeetCode刷题实战403：青蛙过河][LeetCode_401]

[LeetCode刷题实战404：左叶子之和][LeetCode_404]

[LeetCode刷题实战405：数字转换为十六进制数][LeetCode_401]

[LeetCode刷题实战406：根据身高重建队列][LeetCode_401]

[LeetCode刷题实战407：接雨水 II][LeetCode_401]

[LeetCode刷题实战408：有效单词缩写][LeetCode_401]

[LeetCode刷题实战409：最长回文串][LeetCode_409]

[LeetCode刷题实战410：分割数组的最大值][LeetCode_401]

[LeetCode刷题实战411：最短独占单词缩写][LeetCode_401]

[LeetCode刷题实战412：Fizz Buzz][LeetCode_412_Fizz Buzz]

[LeetCode刷题实战413：等差数列划分][LeetCode_401]

[LeetCode刷题实战414：第三大的数][LeetCode_414]

[LeetCode刷题实战415：字符串相加][LeetCode_401]

[LeetCode刷题实战416：分割等和子集][LeetCode_401]

[LeetCode刷题实战417：太平洋大西洋水流问题][LeetCode_417]

[LeetCode刷题实战418：屏幕可显示句子的数量][LeetCode_418]

![078e3d82ad3b9bff3cb7357791e7e12b.png][]

[76cbb20d49a68ba3748f5dbcffa6394d.png]: /images/20220828/507f766a148b4eea827eefa70b96040a.png
[LeetCode1-400]: https://blog.csdn.net/itcodexy/article/details/109832160
[LeetCode_401]: https://blog.csdn.net/itcodexy/article/details/120916108
[LeetCode_402_ K]: https://blog.csdn.net/itcodexy/article/details/120610243
[LeetCode_404]: https://blog.csdn.net/itcodexy/article/details/118402082
[LeetCode_409]: https://blog.csdn.net/itcodexy/article/details/114986911
[LeetCode_412_Fizz Buzz]: https://blog.csdn.net/Jackshijin/article/details/103489372
[LeetCode_414]: https://blog.csdn.net/itcodexy/article/details/120858189
[LeetCode_417]: https://blog.csdn.net/itcodexy/article/details/120929031
[LeetCode_418]: https://blog.csdn.net/lunahaijiao/article/details/105525400
[078e3d82ad3b9bff3cb7357791e7e12b.png]: /images/20220828/237da3838fcb4149abe30bf882a8e5b7.png