甲板上的战舰

419. 甲板上的战舰

给你一个大小为 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'

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

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int countBattleships(vector<vector<char>>& board) { } };

php 解法, 执行用时: 24 ms, 内存消耗: 23.2 MB, 提交时间: 2024-06-11 11:20:39

class Solution {

    /**
     * @param String[][] $board
     * @return Integer
     */
    function countBattleships($board) {
        $m = count($board);
        $n = count($board[0]);
        $ans = 0;
        for ( $i = 0; $i < $m; $i++ ) {
            for ( $j = 0; $j < $n; $j++) {
                if ( $i > 0 && $board[$i - 1][$j] == 'X') continue;
                if ( $j > 0 && $board[$i][$j - 1] == 'X') continue;
                if ( $board[$i][$j] == 'X' ) $ans++;
            }
        }
        return $ans;
    }
}

rust 解法, 执行用时: 0 ms, 内存消耗: 3.8 MB, 提交时间: 2024-06-11 11:18:51

impl Solution {
    pub fn count_battleships(board: Vec<Vec<char>>) -> i32 {
        let mut ans = 0;
        for (i, row) in board.iter().enumerate() {
            for (j, &c) in row.iter().enumerate() {
                if c == 'X' && 
                    (j == 0 || row[j - 1] != 'X') &&
                    (i == 0 || board[i - 1][j] != 'X') {
                    ans += 1;
                }
            }
        }
        ans
    }
}

javascript 解法, 执行用时: 67 ms, 内存消耗: 49.4 MB, 提交时间: 2024-06-11 11:18:41

/**
 * @param {character[][]} board
 * @return {number}
 */
var countBattleships = function(board) {
    let ans = 0;
    for (let i = 0; i < board.length; i++) {
        for (let j = 0; j < board[i].length; j++) {
            if (board[i][j] === 'X' && 
                (j === 0 || board[i][j - 1] !== 'X') && 
                (i === 0 || board[i - 1][j] !== 'X')) {
                ans++;
            }
        }
    }
    return ans;
};

golang 解法, 执行用时: 0 ms, 内存消耗: 2.4 MB, 提交时间: 2024-06-11 11:18:30

func countBattleships(board [][]byte) (ans int) {
    for i, row := range board {
        for j, c := range row {
            if c == 'X' &&
                (j == 0 || row[j-1] != 'X') &&
                (i == 0 || board[i-1][j] != 'X') {
                ans++
            }
        }
    }
    return
}

cpp 解法, 执行用时: 11 ms, 内存消耗: 11.4 MB, 提交时间: 2024-06-11 11:18:21

class Solution {
public:
    int countBattleships(vector<vector<char>>& board) {
        int ans = 0;
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[i].size(); j++) {
                if (board[i][j] == 'X' && 
                    (j == 0 || board[i][j - 1] != 'X') && 
                    (i == 0 || board[i - 1][j] != 'X')) {
                    ans++;
                }
            }
        }
        return ans;
    }
};

python3 解法, 执行用时: 56 ms, 内存消耗: 17 MB, 提交时间: 2022-11-10 21:12:18

class Solution:
    def countBattleships(self, board: List[List[str]]) -> int:
        return sum(ch == 'X' and not (i > 0 and board[i - 1][j] == 'X' or j > 0 and board[i][j - 1] == 'X')
                   for i, row in enumerate(board) for j, ch in enumerate(row))

java 解法, 执行用时: 1 ms, 内存消耗: 41 MB, 提交时间: 2022-11-10 21:11:51

class Solution {
    public int countBattleships(char[][] board) {
        int m = board.length, n = board[0].length;
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i > 0 && board[i - 1][j] == 'X') continue;
                if (j > 0 && board[i][j - 1] == 'X') continue;
                if (board[i][j] == 'X') ans++;
            }
        }
        return ans;
    }
}

python3 解法, 执行用时: 24 ms, 内存消耗: 16.9 MB, 提交时间: 2022-11-10 21:11:14

class Solution:
    def countBattleships(self, board: List[List[str]]) -> int:
        ans = 0
        m, n = len(board), len(board[0])
        for i, row in enumerate(board):
            for j, ch in enumerate(row):
                if ch == 'X':
                    row[j] = '.'
                    for k in range(j + 1, n):
                        if row[k] != 'X':
                            break
                        row[k] = '.'
                    for k in range(i + 1, m):
                        if board[k][j] != 'X':
                            break
                        board[k][j] = '.'
                    ans += 1
        return ans

上一题

下一题

详情