leetcode
leetcode 351 ~ 400
甲板上的战舰

甲板上的战舰

难度:

标签:

题目描述

给你一个大小为 m x n 的矩阵 board 表示甲板,其中,每个单元格可以是一艘战舰 'X' 或者是一个空位 '.' ,返回在甲板 board 上放置的 战舰 的数量。

战舰 只能水平或者垂直放置在 board 上。换句话说,战舰只能按 1 x k1 行,k 列)或 k x 1k 行,1 列)的形状建造,其中 k 可以是任意大小。两艘战舰之间至少有一个水平或垂直的空位分隔 (即没有相邻的战舰)。

 

示例 1:

输入:board = [["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]]
输出:2

示例 2:

输入:board = [["."]]
输出:0

 

提示:

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

 

进阶:你可以实现一次扫描算法,并只使用 O(1) 额外空间,并且不修改 board 的值来解决这个问题吗?

代码结果

运行时间: 21 ms, 内存: 18.2 MB


/*
 * 题目思路:
 * 使用Java Stream API同样可以实现对战舰数量的统计。利用流的遍历特性进行判断,
 * 如果当前格子是'X',且其上边和左边的格子不是'X',则认为这是一个战舰的头部。
 */
import java.util.stream.IntStream;
public class Solution {
    public int countBattleships(char[][] board) {
        return (int) IntStream.range(0, board.length)
            .flatMap(i -> IntStream.range(0, board[0].length)
                .filter(j -> board[i][j] == 'X' && (i == 0 || board[i - 1][j] != 'X') && (j == 0 || board[i][j - 1] != 'X'))
            ).count();
    }
}

解释

方法:

这个题解采用了一次遍历的思路。从矩阵的左上角开始,遍历每个格子。当遇到一个战舰('X')时,将计数器加1,并将该格子标记为已访问('.')。然后向下和向右分别搜索,将连续的战舰格子都标记为已访问,直到遇到空位('.')或越界为止。这样可以确保每个战舰只被计数一次。

时间复杂度:

O(m*n)

空间复杂度:

O(1)

代码细节讲解

🦆
在遍历矩阵时,你是如何决定只在发现'X'的首个单元格时增加战舰计数器,而不是对每个'X'都增加?
在遍历矩阵时,我们只在发现'X'的首个单元格时增加计数器,是因为我们的目标是计数战舰的总数,而不是单个方格。战舰是由连续的'X'组成的,因此,遇到'X'时,我们认为它可能是一个新的战舰的开始。通过从这点向下和向右搜索并标记连续的'X',我们可以确保整艘战舰被处理,从而避免对同一战舰的重复计数。
🦆
为什么在检测到一个'X'后,只向下和向右搜索连续的战舰,而不是向上或向左?
只向下和向右搜索的原因是,我们从矩阵的左上角开始遍历到右下角。当我们在某个位置发现'X'时,该位置左边和上边的所有单元格已经被检查过,因此任何可能连接的战舰部分也应该已经被标记。因此,只需要检查当前位置右边和下边的单元格,从而有效避免重复工作且保持算法效率。
🦆
题解中提到标记已访问的战舰格子为'.',这种修改原数据的方法会不会对问题求解产生其他影响,例如重新运行算法或并行处理?
直接在原数据上进行修改确实可能对其他操作产生影响,如需重复运行算法或进行并行处理时可能会遇到问题。因为一旦原始数据被修改,未来的任何算法或操作都将基于已经改变的数据,这可能导致错误的结果。通常,若原数据需要保留,则应考虑使用额外的数据结构来标记已访问的单元格,或在开始处理前复制一份数据用于操作。
🦆
在代码中,如果遇到一个边界上的战舰(例如在矩阵的最右列或最下行),算法如何确保不会越界?
在代码实现中,通过在while循环条件中检查边界,我们确保了不会越界。例如,在向下搜索时,我们检查'vert < m',确保'vert'索引不会超过矩阵的行数。类似地,在向右搜索时,我们检查'hor < n',确保'hor'索引不会超过矩阵的列数。这些条件确保了即使战舰位于边界上,代码也不会尝试访问不存在的矩阵元素,从而避免越界错误。

相关问题