LeetCode 第419题：甲板上的战舰

📖 文章摘要

本文详细解析LeetCode第419题“甲板上的战舰”，这是一道矩阵遍历问题。文章提供了一种巧妙的一次遍历解法，包含C#、Python、C++三种语言实现，配有详细的分析和性能对比。适合想要提高矩阵处理能力的程序员。

核心知识点： 矩阵遍历、计数问题、空间优化
难度等级： 中等
推荐人群： 具有基础算法知识，想要学习矩阵处理技巧的程序员

题目描述

给你一个大小为 m x n 的矩阵 board 表示甲板，其中，每个单元格可以是一艘战舰 'X' 或者是一个空位 '.' 。

返回在甲板 board 上放置的战舰的数量。

战舰只能水平或者垂直放置在 board 上。换句话说，战舰只能由 1 x k 的连续单元格组成，其中 k 可以是 1 或者一个大于 1 的整数。这些单元格必须在矩阵中连续相邻。

示例

示例 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'

解题思路

这道题有一个巧妙的解法：只需要统计战舰的左上角位置即可。具体来说：

遍历矩阵中的每个位置
如果当前位置是’X’，且其左边和上边都不是’X’，则这个位置是一艘战舰的左上角
统计所有左上角的数量即为战舰数量

图解思路

战舰判断表

位置	左边	上边	是否为战舰起点	说明
X	.	.	是	左上角起点
X	X	.	否	水平战舰中间
X	.	X	否	垂直战舰中间
.	*	*	否	空位

遍历方式分析表

方法	时间复杂度	空间复杂度	优点	缺点
DFS	O(m×n)	O(m×n)	直观	空间占用大
一次遍历	O(m×n)	O(1)	空间优化	需要理解技巧

代码实现

C# 实现

public class Solution {
    public int CountBattleships(char[][] board) {
        int count = 0;
        int m = board.Length;
        int n = board[0].Length;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'X') {
                    // 检查左边和上边是否有X
                    if ((i == 0 || board[i-1][j] != 'X') && 
                        (j == 0 || board[i][j-1] != 'X')) {
                        count++;
                    }
                }
            }
        }
        
        return count;
    }
}

Python 实现

class Solution:
    def countBattleships(self, board: List[List[str]]) -> int:
        count = 0
        m, n = len(board), len(board[0])
        
        for i in range(m):
            for j in range(n):
                if board[i][j] == 'X':
                    # 检查左边和上边是否有X
                    if (i == 0 or board[i-1][j] != 'X') and \
                       (j == 0 or board[i][j-1] != 'X'):
                        count += 1
                        
        return count

C++ 实现

class Solution {
public:
    int countBattleships(vector<vector<char>>& board) {
        int count = 0;
        int m = board.size();
        int n = board[0].size();
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'X') {
                    // 检查左边和上边是否有X
                    if ((i == 0 || board[i-1][j] != 'X') && 
                        (j == 0 || board[i][j-1] != 'X')) {
                        count++;
                    }
                }
            }
        }
        
        return count;
    }
};

执行结果

C# 实现

执行用时：88 ms
内存消耗：38.9 MB

Python 实现

执行用时：72 ms
内存消耗：15.1 MB

C++ 实现

执行用时：4 ms
内存消耗：8.2 MB

性能对比

语言	执行用时	内存消耗	特点
C#	88 ms	38.9 MB	性能适中，内存占用较大
Python	72 ms	15.1 MB	执行较快，内存占用中等
C++	4 ms	8.2 MB	执行最快，内存占用最小

代码亮点

🎯 巧妙利用战舰的左上角特征进行计数
💡 无需额外空间即可完成统计
🔍 边界条件处理简洁优雅
🎨 代码结构清晰，易于理解和维护

常见错误分析

🚫 使用DFS导致不必要的空间开销
🚫 没有正确处理边界条件
🚫 重复计数相同的战舰
🚫 忽略了战舰只能水平或垂直放置的条件

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
DFS	O(m×n)	O(m×n)	思路直观	空间复杂度高
一次遍历	O(m×n)	O(1)	空间复杂度低	需要理解技巧
并查集	O(m×n×α(m×n))	O(m×n)	可扩展性强	实现复杂

📖 系列导航

🔥 LeetCode 题解合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第419题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

👍 点个赞，让更多人看到这篇文章
📁 收藏文章，方便后续查阅复习
🔔 关注作者，获取更多高质量算法题解
💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！

📖 文章摘要

题目描述

示例

示例 1：

示例 2：

提示

解题思路

图解思路

战舰判断表

遍历方式分析表

代码实现

C# 实现

Python 实现

C++ 实现

执行结果

C# 实现

Python 实现

C++ 实现

性能对比

代码亮点

常见错误分析

解法对比

相关题目

📖 系列导航

💬 互动交流