leetcode算法题：岛屿数量

leetcode算法题200
链接：https://leetcode.cn/problems/number-of-islands

题目

你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

输入：grid = [
[“1”,“1”,“1”,“1”,“0”],
[“1”,“1”,“0”,“1”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“0”,“0”,“0”]
]
输出：1
示例 2：

输入：grid = [
[“1”,“1”,“0”,“0”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“1”,“0”,“0”],
[“0”,“0”,“0”,“1”,“1”]
]
输出：3

解法

1、感染

	public static int numIslands(char[][] grid) {
		int num = 0;
		int X = grid.length;
		for (int i = 0; i < X; i++) {
			int Y = grid[i].length;
			for (int j = 0; j < Y; j++) {
				if (grid[i][j] == '1') {
					num++;
					// 填充设置岛屿
					infect(grid, i, j);
				}
			}
		}
		return num;
	}

	public static void infect(char[][] grid, int x, int y) {
		if (x < 0 || x == grid.length || y < 0 || y == grid[0].length || grid[x][y] != '1') {
			return;
		}
		grid[x][y] = '0';
		infect(grid, x - 1, y);
		infect(grid, x + 1, y);
		infect(grid, x, y - 1);
		infect(grid, x, y + 1);
	}

2、并查集

和之前的省份数量有点类似，这里取巧了一下，使用一维数组来存储所有情况，通过x * col + y算出下标

	public static int numIslands2(char[][] grid) {
		if (null == grid || grid.length == 0) {
			return 0;
		}
		int row = grid.length;
		int col = grid[0].length;
		UnionFind unionFind = new UnionFind(grid);
		// 0列特殊处理，后面不用判断边界
		for (int i = 1; i < row; i++) {
			if (grid[i - 1][0] == '1' && grid[i][0] == '1') {
				unionFind.union(i - 1, 0, i, 0);
			}
		}

		// 0行特殊处理，后面不用判断边界
		for (int i = 1; i < col; i++) {
			if (grid[0][i - 1] == '1' && grid[0][i] == '1') {
				unionFind.union(0, i - 1, 0, i);
			}
		}

		for (int i = 1; i < grid.length; i++) {
			for (int j = 1; j < grid[i].length; j++) {
				if (grid[i][j] == '1') {
					if (grid[i - 1][j] == '1') {
						unionFind.union(i, j, i - 1, j);
					}
					if (grid[i][j - 1] == '1') {
						unionFind.union(i, j, i, j - 1);
					}
				}
			}
		}

		return unionFind.getSize();
	}

	public static class UnionFind {
		private int[] parents;
		private int[] childSizes;
		/**
		 * 每行有多少个
		 */
		private int col;
		/**
		 * 一共有多少个集合（岛）
		 */
		private int size;

		public UnionFind(char[][] data) {
			int row = data.length;
			col = data[0].length;
			int len = row * col;
			parents = new int[len];
			childSizes = new int[len];
			for (int i = 0; i < row; i++) {
				for (int j = 0; j < col; j++) {
					if (data[i][j] == '1') {
						int index = getIndex(i, j);
						parents[index] = index;
						childSizes[index] = 1;
						size++;
					}
				}
			}
		}

		//	坐标换成点 （x,y)->point
		public int getIndex(int x, int y) {
			return x * col + y;
		}

		public int findParent(int index) {
			Stack<Integer> stack = new Stack<>();
			while (index != parents[index]) {
				stack.push(index);
				index = parents[index];
			}

			while (!stack.isEmpty()) {
				parents[stack.pop()] = index;
			}
			return index;
		}

		public void union(int x1, int y1, int x2, int y2) {
			int index1 = getIndex(x1, y1);
			int index2 = getIndex(x2, y2);
			int parent1 = findParent(index1);
			int parent2 = findParent(index2);
			if (parent1 != parent2) {
				if (childSizes[parent1] >= childSizes[parent2]) {
					childSizes[parent1] += childSizes[parent2];
					parents[parent2] = parent1;
				} else {
					childSizes[parent2] += childSizes[parent1];
					parents[parent1] = parent2;
				}
				size--;
			}
		}

		public int getSize() {
			return size;
		}

	}