甲板上的战舰-LeetCode

甲板上的战舰

🎯 问题描述（来源于LeetCode）

描述：
给你一个大小为 m x n 的矩阵 board 表示棋盘，其中，每个单元格可以是一艘战舰 'X' 或者是一个空位 '.' 
舰队 只能水平或者垂直放置在 board 上。换句话说，舰队只能按 1 x k（1 行，k 列）或 k x 1（k 行，1 列）的形状放置，其中 k 可以是任意大小。两个舰队之间至少有一个水平或垂直的空格分隔 （即没有相邻的舰队）。
要求：
返回在棋盘 board 上放置的 舰队 的数量。
说明：

• m == board.length
• n == board[i].length
• 1 <= m, n <= 200
• board[i][j] 是 '.' 或 'X'

示例：

• 示例 1：
  输入：board = [[“X”,“.”,“.”,“X”],[“.”,“.”,“.”,“X”],[“.”,“.”,“.”,“X”]]
  输出：2
• 示例 2：
  输入: board = [[“.”]]
  输出: 0

💻 解题思路

思路1：找到舰队头部

思路1：代码实现

class Solution:
    def countBattleships(self, board: List[List[str]]) -> int:
        count=0
        m,n=len(board),len(board[0])
        for i,j in product(range(m),range(n)):
            if board[i][j]=='X' and (board[i-1][j]=='.'or i==0)and (board[i][j-1]=='.' or j==0) :
                count+=1
        return count        
          

思路1：📊 性能分析

提交结果

• 运行时间：4ms击败31.75%
• 内存消耗：19.43MB击败98.41%

复杂度验证

• 时间复杂度：$O(m*n)$
• 空间复杂度：$O(1)$

思考

观察图形，舰队头部的左边和上边都没有战舰（除非是边界）统计舰队头部数量即是舰队数量