419. 甲板上的战舰.md

419. 甲板上的战舰

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

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

示例 :

X..X
...X
...X

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

无效样例 :

...X
XXXX
...X

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

进阶:

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

思路

1、题目中指出，战舰要么是横着连续，要么是竖着连续 2、遍历数组，当遇到'X'就说明有一艘战舰，我们判断是横着还是竖着，循环把战舰的'X'全部设为"." 3、继续循环，下次遇到'X'说明是新的战舰，我们再记一次数，重复操作2 4、当遍历完数组，甲板就全变成了"."，所有的战舰也被统计出来了

代码

/**
 * @param {character[][]} board
 * @return {number}
 */
function countBattleships(board) {
  let count = 0;
  for (let i = 0; i < board.length; i++) {
    let row = board[i];
    for (let j = 0; j < row.length; j++) {
      if (row[j] === 'X') {
        if (board[i + 1] && board[i + 1][j] === 'X') {
          let r = i;
          while (board[r] && board[r][j] === 'X') {
            board[r++][j] = '.';
          }
        } else {
          let c = j;
          while (row[c] === 'X') {
            row[c++] = '.';
          }
        }
        count++;
      }
    }
  }
  return count;
}

复杂度分析

时间复杂度 $O(N^2)$

空间复杂度 $O(N)$