419.battleships-in-a-board.md

给定一个二维的甲板， 请计算其中有多少艘战舰。  战舰用  'X'表示，空位用  '.'表示。  你需要遵守以下规则：

给你一个有效的甲板，仅由战舰或者空位组成。 战舰只能水平或者垂直放置。换句话说,战舰只能由  1xN (1 行, N 列)组成，或者  Nx1 (N 行, 1 列)组成，其中 N 可以是任意大小。 两艘战舰之间至少有一个水平或垂直的空位分隔  - 即没有相邻的战舰。 示例 :

X..X ...X ...X 在上面的甲板中有 2 艘战舰。

无效样例 :

...X XXXX ...X 你不会收到这样的无效甲板  - 因为战舰之间至少会有一个空位将它们分开。

进阶:

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

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/battleships-in-a-board 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

一次扫描，O(1)额外空间，使用原地算法

var countBattleships = function (board) {
  let counter = 0;
  let dirX = [0, 0, -1, 1], // 上， 下，左，右
    dirY = [-1, 1, 0, 0];
  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board[0].length; j++) {
      if (board[i][j] == "X") {
        counter++;
        board[i][j] == ".";
        for (let k = 0; k < 4; k++) {
          // 四个方向消除 X
          let x = dirX[k] + i,
            y = dirY[k] + j;
          while (
            x >= 0 &&
            x < board.length &&
            y >= 0 &&
            y < board[0].length &&
            board[x][y] == "X"
          ) {
            board[x][y] = ".";
            x += dirX[k];
            y += dirY[k];
          }
        }
      }
    }
  }
  return counter;
};

只要判断左上角为 X 的个数

var countBattleships = function (board) {
  let counter = 0;
  let dirX = [0, 0, -1, 1], // 上，下，左，右
    dirY = [-1, 1, 0, 0];
  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board[0].length; j++) {
      if (board[i][j] == "X") {
        // 如果左边和上边都没有X,说明是左上角
        let lx = i - 1,
          ly = j,
          ux = i,
          uy = j - 1;
        if (
          !(lx >= 0 && board[lx][ly] == "X") &&
          !(uy >= 0 && board[ux][uy] == "X")
        )
          counter++;
      }
    }
  }
  return counter;
};

方法一：一次扫描，O(1)额外空间，使用原地算法将找过的'X'替换为’.‘

var countBattleships = function (board) {
  let counter = 0;
  let dirX = [0, 0, -1, 1], // 上， 下，左，右
    dirY = [-1, 1, 0, 0];
  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board[0].length; j++) {
      if (board[i][j] == "X") {
        counter++;
        board[i][j] == ".";
        for (let k = 0; k < 4; k++) {
          // 四个方向消除 X
          let x = dirX[k] + i,
            y = dirY[k] + j;
          while (
            x >= 0 &&
            x < board.length &&
            y >= 0 &&
            y < board[0].length &&
            board[x][y] == "X"
          ) {
            board[x][y] = ".";
            x += dirX[k];
            y += dirY[k];
          }
        }
      }
    }
  }
  return counter;
};

方法二： 只统计左上角的 X 的个数

var countBattleships = function (board) {
  let counter = 0;
  let dirX = [0, 0, -1, 1], // 上，下，左，右
    dirY = [-1, 1, 0, 0];
  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board[0].length; j++) {
      if (board[i][j] == "X") {
        // 如果左边和上边都没有X,说明是左上角
        let lx = i - 1,
          ly = j,
          ux = i,
          uy = j - 1;
        if (
          !(lx >= 0 && board[lx][ly] == "X") &&
          !(uy >= 0 && board[ux][uy] == "X")
        )
          counter++;
      }
    }
  }
  return counter;
};