力扣leetcode 827. 最大人工岛

题目链接与描述

https://leetcode.cn/problems/making-a-large-island/
给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。

返回执行此操作后，grid 中最大的岛屿面积是多少？

岛屿 由一组上、下、左、右四个方向相连的 1 形成。

示例 1:

输入: grid = [[1, 0], [0, 1]]
输出: 3
解释: 将一格0变成1，最终连通两个小岛得到面积为 3 的岛屿。
示例 2:

输入: grid = [[1, 1], [1, 0]]
输出: 4
解释: 将一格0变成1，岛屿的面积扩大为 4。
示例 3:

输入: grid = [[1, 1], [1, 1]]
输出: 4
解释: 没有0可以让我们变成1，面积依然为 4。

提示：

n == grid.length
n == grid[i].length
1 <= n <= 500
grid[i][j] 为 0 或 1

关键词：hash表

方法一：

运行截图

代码

	public int largestIsland(int[][] grid) {
		// grid.length >= 1 的矩形
		// 结果数和岛屿编号
		int result = 0, index = 2;
		// 岛屿 map
		HashMap<Integer, Integer> areasMap = new HashMap<>();
		// 遍历所有点
		for (int i = 0; i < grid.length; i++) {
			for (int j = 0; j < grid[i].length; j++) {
				// 如果遇到岛屿
				if (grid[i][j] == 1) {
					// 将编号和计算得到的数映射
					areasMap.put(index, calculateAreas(index++, grid, i, j)); // 只计算未编号的岛屿
				}
			}
		}

		// 没有岛屿，全是海洋
		if (areasMap.size() == 0) {
			return 1;
		}
		for (int i = 0; i < grid.length; i++) {
			for (int j = 0; j < grid[i].length; j++) {
				if (grid[i][j] == 0) {
					// 把是岛屿的编号取出来
					Set<Integer> islands = getIslands(grid, i, j);
					if (islands.size() == 0) {
						continue; // 周围没有岛屿
					}
					// 把所有存在的岛屿 累加起来 比较取更大的
					result = Math.max(result, islands.stream().map(areasMap::get).reduce(Integer::sum).orElse(0) + 1);
				}
			}
		}
		// 如果结果是0
		if (result == 0) {
			// 全是岛屿，没有海洋
			return areasMap.get(2);
		}
		return result;
	}


	public int calculateAreas(int index, int[][] grid, int row, int column) {
		// dfs 并且标记已遍历的岛屿
		if (!isLegal(grid, row, column) || grid[row][column] != 1) {
			return 0;
		}
		// 记录index
		grid[row][column] = index;
		// 上下左右 深度遍历 然后加上自身
		return calculateAreas(index, grid, row + 1, column) + calculateAreas(index, grid, row - 1, column) + calculateAreas(index, grid, row, column - 1) + calculateAreas(index, grid, row, column + 1) + 1;
	}

	public boolean isLegal(int[][] grid, int row, int column) {
		return row >= 0 && row < grid.length && column >= 0 && column < grid[0].length;
	}

	public Set<Integer> getIslands(int[][] grid, int row, int column) {
		Set<Integer> result = new HashSet<>();
		if (isLegal(grid, row + 1, column) && grid[row + 1][column] != 0) {
			result.add(grid[row + 1][column]);
		}
		if (isLegal(grid, row - 1, column) && grid[row - 1][column] != 0) {
			result.add(grid[row - 1][column]);
		}
		if (isLegal(grid, row, column - 1) && grid[row][column - 1] != 0) {
			result.add(grid[row][column - 1]);
		}
		if (isLegal(grid, row, column + 1) && grid[row][column + 1] != 0) {
			result.add(grid[row][column + 1]);
		}
		return result;
	}

结尾

欢迎评论区交流，每日打卡，冲冲冲！！！