✨今天给大家带来的是LeetCode上的第419题——甲板上的战舰(LeetCode 419. Battleships in a Board✨。这道题目是一个经典的二维数组遍历问题，要求我们在一个棋盘中找到所有的战舰。接下来给大家详细讲解一下解题思路和主要的数据结构哦~🥳
题目描述
我们有一个二维数组，代表一个战舰棋盘。棋盘中的每个元素是 ‘X’ 或 ‘.’。‘X’ 代表战舰的一部分，‘.’ 代表水域。战舰只能水平或垂直放置，且战舰之间至少有一个空位（即不相邻）。我们的目标是统计棋盘中战舰的数量。
解题思路💡
1. 一次扫描
我们只需要一次扫描整个棋盘就能解决这个问题。扫描过程中，遇到战舰的起点时计数。
2. 战舰的起点
战舰的起点定义为左上角的‘X’，即它的左边和上边都不是‘X’。
3. 过滤条件
在扫描的过程中，我们需要判断每个‘X’是否是战舰的起点，如果是，则计数+1。
为什么想到这样做？
这种方法利用了战舰只能水平或垂直放置且不相邻的特性，通过一次遍历就能准确统计出所有战舰的数量：
如果当前的‘X’的上方或左方有‘X’，那么它一定不是战舰的起点，因为它已经是一个战舰的一部分。
只有当‘X’的上方和左方都不是‘X’时，它才是一个新的战舰的起点。
通过这种方法，我们可以在不修改棋盘的前提下，使用 O(1) 的额外空间解决问题，非常高效。
主要数据结构
这道题目主要使用了二维数组进行遍历和判断。通过两个嵌套循环遍历整个数组，再通过条件判断找到战舰的起点。
代码实现📋
以下是Scala语言的实现代码，非常简洁哦~
object Solution {
def countBattleships(board: Array[Array[Char]]): Int = {
var count = 0
for (i <- board.indices; j <- board(i).indices if board(i)(j) == 'X') {
if ((i == 0 || board(i - 1)(j) != 'X') && (j == 0 || board(i)(j - 1) != 'X')) {
count += 1
}
}
count
}
}
代码说明：
board.indices：遍历行索引board(i).indices：遍历列索引if board(i)(j) == 'X'：过滤条件，只对‘X’进行处理if ((i == 0 || board(i - 1)(j) != 'X') && (j == 0 || board(i)(j - 1) != 'X'))：判断是否是战舰的起点
小结🔍
这道题目主要考察了二维数组的遍历和条件判断，通过一次扫描和O(1)的额外空间解决了问题，是一道非常经典的二维数组题目。希望大家能通过这道题目巩固二维数组的相关知识点哦~😊
#LeetCode #每日一题 #算法 #数据结构 #Scala #战舰棋盘
希望这个博客能帮到你哦！如果有任何问题或者建议，欢迎在评论区留言~❤️
