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 的值来解决这个问题吗？

解题思路

遍历数组，判断当前找出所有“战舰”的左上角即可，假设（i,j）为战舰的左上角，则其需要满足以下条件：

• 1、board[i][j] = ‘X’
• 2、(i == 0 || board[i - 1][j] === “.”) && (j == 0 || board[i][j - 1] === “.”)

遍历整个二维数组，统计“战舰”的左上角数量即可，完整代码如下：

AC代码

/**
 * @param {character[][]} board
 * @return {number}
 */
var countBattleships = function (board) {
  let cnt = 0;
  const check = (i, j) => {
    return (
      (i == 0 || board[i - 1][j] === ".") && (j == 0 || board[i][j - 1] === ".")
    );
  };
  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board[i].length; j++) {
      if (board[i][j] === "X" && check(i, j)) cnt++;
    }
  }
  return cnt;
};

公众号

关注公众号『前端也能这么有趣』，获取更多有趣内容。

说在后面

🎉 这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球 🏸 ，平时也喜欢写些东西，既为自己记录 📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解 🙇，写错的地方望指出，定会认真改进 😊，偶尔也会在自己的公众号『前端也能这么有趣』发一些比较有趣的文章，有兴趣的也可以关注下。在此谢谢大家的支持，我们下文再见 🙌。