当前位置：首页 > article >正文

LeetCode题练习与总结：棋盘上的战舰--419

article 2024/11/25 11:02:54

一、题目描述

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

舰队只能水平或者垂直放置在 board 上。换句话说，舰队只能按 1 x k（1 行，k 列）或 k x 1（k 行，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'

二、解题思路

遍历整个棋盘 board。
当遇到一个 ‘X’ 时，判断它是否是一艘新舰队的起始位置。
一个 ‘X’ 是新舰队的起始位置的判断条件是：它不是在第一行但是它上方是 ‘.’, 或者它不是在第一列但是它左方是 ‘.’。
如果一个 ‘X’ 是新舰队的起始位置，则将舰队数量加一。
继续遍历，直到整个棋盘被遍历完毕。
返回舰队数量。

三、具体代码

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++) {
                // 如果当前单元格是 'X'，并且上方和左方都是 '.' 或者边界之外，则它是一艘新舰队的起始位置
                if (board[i][j] == 'X' && 
                    (i == 0 || board[i - 1][j] == '.') && 
                    (j == 0 || board[i][j - 1] == '.')) {
                    count++; // 舰队数量加一
                }
            }
        }
        
        return count; // 返回舰队数量
    }
}

四、时间复杂度和空间复杂度

1. 时间复杂度

该算法使用了两个嵌套的 for 循环来遍历整个棋盘 board。
外层循环遍历行，内层循环遍历列，每个循环的次数都是固定的。
外层循环运行 m 次（棋盘的行数），内层循环运行 n 次（棋盘的列数）。
因此，算法的时间复杂度是 O(m * n)，其中 m 是棋盘的行数，n 是棋盘的列数。

2. 空间复杂度

该算法只使用了常数个额外空间，即变量 count 用于计数，变量 m 和 n 分别用于存储棋盘的行数和列数。
这些额外空间的大小不随输入棋盘的大小而变化。
因此，算法的空间复杂度是 O(1)，表示使用了常数级别的额外空间。

五、总结知识点

类定义：
- class Solution：定义了一个名为 Solution 的类。
方法定义：
- public int countBattleships(char[][] board)：定义了一个公共方法 countBattleships，它接受一个二维字符数组 board 作为参数，并返回一个整数。
变量声明和初始化：
- int count = 0：声明并初始化一个整数变量 count 用于计数。
- int m = board.length：声明并初始化一个整数变量 m，它保存输入二维数组的行数。
- int n = board[0].length：声明并初始化一个整数变量 n，它保存输入二维数组的第一行的列数。
循环结构：
- for (int i = 0; i < m; i++)：使用一个 for 循环来遍历二维数组的每一行。
- for (int j = 0; j < n; j++)：嵌套的 for 循环用于遍历每一行的每个元素。
条件判断：
- if (board[i][j] == 'X' && (i == 0 || board[i - 1][j] == '.') && (j == 0 || board[i][j - 1] == '.'))：使用 if 语句和逻辑与操作符 && 来检查当前元素是否是 ‘X’，并且它上方和左方是否为 ‘.’ 或者它位于边界上。
数组访问：
- board[i][j]：通过索引访问二维数组中的元素。
边界条件处理：
- (i == 0 || board[i - 1][j] == '.')：检查当前元素是否位于第一行或者它上方元素是否为 ‘.’。
- (j == 0 || board[i][j - 1] == '.')：检查当前元素是否位于第一列或者它左方元素是否为 ‘.’。
自增操作：
- count++：使用自增操作符来增加舰队的计数。
返回值：
- return count;：返回计数结果，即舰队的数量。