🌕🌗 419. 甲板上的战舰

难度: 🌕🌗

问题描述

---

解法

class Solution {
    public int countBattleships(char[][] board) {
        // 思路：
        // 题意中给定的 board 数组本身满足如果存在战舰，那么战舰之间必然满足空位分隔条件
        // 要想一遍扫描 & 空间复杂度为 O(1)
        // 那么如果可以找到 舰头 的位置，就可以得出战舰的数量
        // 舰头的特征是：
        // 左边为空 && 上边为空
        int row = board.length;
        int col = board[0].length;
        int res = 0;
        for(int i = 0; i < row; i ++) {
            for(int j = 0; j < col; j ++) {
                if(board[i][j] == 'X') {
                    // 是战舰的一部分，判断是否为舰头
                    if((i == 0 || board[i - 1][j] == '.') && (j == 0 || board[i][j - 1] == '.')) {
                        // 是舰头
                        res ++;
                    }
                }
            }
        }
        return res;
    }
}

---

输出