跳至正文

每日一题——419. 甲板上的战舰

419. 甲板上的战舰

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

战舰 只能水平或者垂直放置在 board 上。换句话说,战舰只能按 1 x k(1 行,k 列)或 k x 1(k 行,1 列)的形状建造,其中 k 可以是任意大小。两艘战舰之间至少有一个水平或垂直的空位分隔 (即没有相邻的战舰)。

public class Solution {
    public int CountBattleships(char[][] board) {
        int m = board.GetLength(0);
        int n = board[0].Length;
        int ans = 0;
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(board[i][j] == 'X' && 
                (i == 0 || board[i-1][j] != 'X') && 
                (j == 0 || board[i][j-1] != 'X')) 
                {
                    ans++;
                }                
            }    
        }
    
        return ans;
    }
}

这个题目最关键的一点测试用例其实是没有不符合战舰排列的情况

也就是说题目说战舰怎么排,输入的数据就一定是这么排的

那这题做起来其实就容易多了

从左上到右下开始扫描

如果在上边界或者左边界遇到X的就一定是一艘战舰了

那如果不在边界上呢?

因为我们是从上到下从左到右开始扫描

那就判断它的上边是不是空格

判断它的左边是不是空格

因为战舰周围一定不能是X

所以只要符合条件的就也是战舰

这样就不需要引入什么bool来记录自己遍历过的数据了

 

发表评论

您的电子邮箱地址不会被公开。