建造一个大的岛屿-数据结构与算法(中)

当前位置:　首页>> 技术小册>> 数据结构与算法(中)

难度:
Hard

题意：

1. 给定一张矩阵图
2. 如果两个点相邻且都为1，这两个点连通
3. 至多把一个0改为1，问最大的连通岛的面积是多大

思路：

- 看数据结构，横竖最大是50，整个图最多才2500个点，直接枚举所有的0，改成1之后做dfs判断连通图，都可以解决
- 两个连通岛其实是两个集合，如果将一个0改成1，意味着把上下左右所在的岛都合并在一个集合中，我们需要一个数据结构，既可以将集合合并，又可以判断某两个元素是否在同一个集合中，这种数据结构就是并查集

解法：

```java
class Solution {
	 private class Set {

int[] s;
        int[] num;
        int r;
        int c;

private Set(int r, int c) {
            this.r = r;
            this.c = c;
            this.s = new int[r * c];
            this.num = new int[r * c];
            for (int i = 0;i < this.s.length;i++) {
                this.s[i] = i;
                this.num[i] = 1;
            }
        }

private int calIdx(int x, int y) {
            return x * c + y;
        }

private int find(int idx) {
            if (this.s[idx] == idx) {
                return idx;
            } else {
                return this.s[idx] = find(this.s[idx]);
            }
        }

private void merge(int x1, int y1, int x2, int y2) {
            int p1 = find(calIdx(x1, y1));
            int p2 = find(calIdx(x2, y2));
            if (p1 != p2) {
                this.s[p1] = p2;
                this.num[p2] += this.num[p1];
            }
        }

}

public int largestIsland(int[][] grid) {
        int[] dx = new int[]{0,0,1,-1};
        int[] dy = new int[]{1,-1,0,0};
        Set set = new Set(grid.length, grid[0].length);
        for (int i = 0;i < grid.length;i++) {
            for (int j = 0;j < grid[0].length;j++) {
                if (grid[i][j] == 0) {
                    continue;
                }
                for (int k = 0;k < 4;k++) {
                    if (i + dx[k] < 0 || i + dx[k] >= grid.length) {
                        continue;
                    }
                    if (j + dy[k] < 0 || j + dy[k] >= grid[0].length) {
                        continue;
                    }
                    if (grid[i + dx[k]][j + dy[k]] == 0) {
                        continue;
                    }
                    set.merge(i, j, i + dx[k], j + dy[k]);
                }
            }
        }

int max = 0;
        for (int i = 0;i < grid.length;i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    continue;
                }

HashSet<Integer> t = new HashSet<>();
                for (int k = 0;k < 4;k++) {
                    if (i + dx[k] < 0 || i + dx[k] >= grid.length) {
                        continue;
                    }
                    if (j + dy[k] < 0 || j + dy[k] >= grid[0].length) {
                        continue;
                    }
                    if (grid[i + dx[k]][j + dy[k]] == 0) {
                        continue;
                    }

t.add(set.find(set.calIdx(i + dx[k], j + dy[k])));
                }

int ret = 0;
                for (Integer p: t) {
                    ret += set.num[p];
                }
                ret ++;
                max = Math.max(ret, max);
            }
        }
        if (max == 0) {
            max = grid.length * grid[0].length;
        }
        return max;
    }
}
```

该分类下的相关小册推荐：

数据结构与算法(上)

编程之道-算法面试(上)

编程之道-算法面试(下)

算法面试通关 50 讲

数据结构与算法之美

业务开发实用算法精讲

数据结构与算法(下)