200. Number of Islands

原题：200. Number of Islands

方法一

思路：路径染色

时间复杂度：O(n^2)

// Runtime: 80 ms, faster than 29.80% of JavaScript online submissions for Number of Islands.
// Memory Usage: 37.2 MB, less than 100.00% of JavaScript online submissions for Number of Islands.
var numIslands = function (grid) {
  if (!grid || !grid.length) {
    return 0;
  }
  const dx = [-1, 0, 1, 0]; //四连通图，注意这里不能把上、左方向省略，原因请看test case3
  const dy = [0, 1, 0, -1];
  const m = grid.length;
  const n = grid[0].length;
  let count = 0;
  const helper = function (i, j) {
    //这里用BFS（队列）或者DFS（递归）做都可以
    if (i < 0 || j < 0 || i >= m || j >= n || grid[i][j] != "1") {
      return;
    }
    grid[i][j] = 0; //染色
    for (let k = 0; k < 4; k++) {
      helper(i + dx[k], j + dy[k]);
    }
  };
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === "1") {
        helper(i, j);
        count++;
      }
    }
  }

  return count;
};

方法二

思路：并查集

时间复杂度：O(n^2)

UFS的代码可参考 并查集的实现

// Runtime: 180 ms, faster than 5.23% of JavaScript online submissions for Number of Islands.
// Memory Usage: 40.1 MB, less than 32.26% of JavaScript online submissions for Number of Islands.
var numIslands = function (grid) {
  if (!grid || !grid.length) {
    return 0;
  }
  const ufs = new UFS();
  const m = grid.length;
  const n = grid[0].length;
  const transform = function (i, j) {
    //展平二维数组
    return i * m + j;
  };

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === "1") {
        ufs.makeSet(transform(i, j));
      }
    }
  }

  const dx = [-1, 0, 1, 0]; //四连通图，注意这里不能把上、左方向省略，原因请看test case3
  const dy = [0, 1, 0, -1];
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === "1") {
        for (let k = 0; k < 4; k++) {
          const di = i + dx[k];
          const dj = j + dy[k];
          if (di >= 0 && dj >= 0 && di < m && dj < n && grid[di][dj] === "1") {
            ufs.union(transform(i, j), transform(di, dj));
          }
        }
      }
    }
  }

  const set = new Set();
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === "1") {
        set.add(ufs.find(transform(i, j)));
      }
    }
  }

  return set.size;
};

test("test1", () => {
  expect(
    numIslands([
      ["1", "1", "1", "1", "0"],
      ["1", "1", "0", "1", "0"],
      ["1", "1", "0", "0", "0"],
      ["0", "0", "0", "0", "0"],
    ])
  ).toEqual(1);
});

test("test2", () => {
  expect(
    numIslands([
      ["1", "1", "0", "0", "0"],
      ["1", "1", "0", "0", "0"],
      ["0", "0", "1", "0", "0"],
      ["0", "0", "0", "1", "1"],
    ])
  ).toEqual(3);
});

test("test2", () => {
  expect(
    numIslands([
      ["1", "1", "1"],
      ["0", "1", "0"],
      ["1", "1", "1"],
    ])
  ).toEqual(1);
});

test cases

test("test1", () => {
  expect(
    numIslands([
      ["1", "1", "1", "1", "0"],
      ["1", "1", "0", "1", "0"],
      ["1", "1", "0", "0", "0"],
      ["0", "0", "0", "0", "0"],
    ])
  ).toEqual(1);
});

test("test2", () => {
  expect(
    numIslands([
      ["1", "1", "0", "0", "0"],
      ["1", "1", "0", "0", "0"],
      ["0", "0", "1", "0", "0"],
      ["0", "0", "0", "1", "1"],
    ])
  ).toEqual(3);
});

test("test2", () => {
  expect(
    numIslands([
      ["1", "1", "1"],
      ["0", "1", "0"],
      ["1", "1", "1"],
    ])
  ).toEqual(1);
});

总结

路径染色更高效，并查集更符合直觉。