827. 最大人工島 : 簡單「並查集 + 枚舉」運用題
題目描述
這是 LeetCode 上的 827. 最大人工島 ，難度為 困難 。
Tag : 「並查集」、「枚舉」
給你一個大小為 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
並查集 + 枚舉
為了方便，我們令 grid
為 g
。
根據題意，容易想到通過「並查集」來維護所有連通塊大小，再通過「枚舉」來找最優翻轉點。
具體的，我們可以先使用「並查集」維護所有 $g[i][j] = 1$ 的塊連通性，並在維護連通性的過程中，使用 sz[idx]
記錄下每個連通塊的大小（注意：只有連通塊根編號， sz[idx]
才有意義，即只有 sz[find(x)]
才有意義）。
隨後我們再次遍歷 g
，根據原始的 $g[i][j]$ 的值進行分別處理：
root tot
最後對所有連通塊大小取最大值即是答案。
一些細節：為了方便，我們令點 $(i, j)$ 的編號從 $1$ 開始；
同時由於我們本身就要用 sz
數組，因此我們可以隨手把並查集的「按秩合併」也加上。體現在 union
操作時，我們總是將小的連通塊合併到大的連通塊上，從而確保我們並查集單次操作即使在最壞情況下複雜度仍為 $O(\alpha(n))$（可看作常數）。需要注意只有同時應用「路徑壓縮」和「按秩合併」，並查集操作複雜度才為 $O(\alpha(n))$。
Java 代碼：
class Solution {
static int N = 510;
static int[] p = new int[N * N], sz = new int[N * N];
int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
void union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return ;
if (sz[ra] > sz[rb]) {
union(b, a);
} else {
sz[rb] += sz[ra]; p[ra] = p[rb];
}
}
public int largestIsland(int[][] g) {
int n = g.length;
for (int i = 1; i <= n * n; i++) {
p[i] = i; sz[i] = 1;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (g[i][j] == 0) continue;
for (int[] di : dirs) {
int x = i + di[0], y = j + di[1];
if (x < 0 || x >= n || y < 0 || y >= n || g[x][y] == 0) continue;
union(i * n + j + 1, x * n + y + 1);
}
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (g[i][j] == 1) {
ans = Math.max(ans, sz[find(i * n + j + 1)]);
} else {
int tot = 1;
Set<Integer> set = new HashSet<>();
for (int[] di : dirs) {
int x = i + di[0],y = j + di[1];
if (x < 0 || x >= n || y < 0 || y >= n || g[x][y] == 0) continue;
int root = find(x * n + y + 1);
if (set.contains(root)) continue;
tot += sz[root];
set.add(root);
}
ans = Math.max(ans, tot);
}
}
}
return ans;
}
}
TypeScript 代碼：
const N = 510
const p = new Array<number>(N * N).fill(-1), sz = new Array<number>(N * N).fill(1)
const dirs = [[1,0], [-1,0], [0,1], [0,-1]]
function find(x: number): number {
if (p[x] != x) p[x] = find(p[x])
return p[x]
}
function union(a: number, b: number): void {
const ra = find(a), rb = find(b)
if (ra == rb) return
if (sz[ra] > sz[rb]) {
union(rb, ra)
} else {
sz[rb] += sz[ra]; p[ra] = p[rb]
}
}
function largestIsland(g: number[][]): number {
const n = g.length
for (let i = 1; i <= n * n; i++) {
p[i] = i; sz[i] = 1
}
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (g[i][j] == 0) continue
for (const di of dirs) {
const x = i + di[0], y = j + di[1]
if (x < 0 || x >= n || y < 0 || y >= n || g[x][y] == 0) continue
union(i * n + j + 1, x * n + y + 1)
}
}
}
let ans = 0
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (g[i][j] == 1) {
ans = Math.max(ans, sz[find(i * n + j + 1)])
} else {
let tot = 1
const set = new Set()
for (let di of dirs) {
const x = i + di[0], y = j + di[1]
if (x < 0 || x >= n || y < 0 || y >= n || g[x][y] == 0) continue
const root = find(x * n + y + 1)
if (set.has(root)) continue
tot += sz[root]
set.add(root)
}
ans = Math.max(ans, tot)
}
}
}
return ans
};
Python 代碼：
class Solution:
def find(self, p, x):
if p[x] != x:
p[x] = self.find(p, p[x])
return p[x]
def union(self, p, sz, a, b):
ra, rb = self.find(p, a), self.find(p, b)
if ra == rb:
return
if sz[ra] > sz[rb]:
ra, rb = rb, ra
sz[rb] += sz[ra]
p[ra] = p[rb]
def largestIsland(self, g: List[List[int]]) -> int:
n, ans = len(g), 0
p, sz = [i for i in range(n * n + 10)], [1 for _ in range(n * n + 10)]
dirs = [[1,0],[-1,0],[0,1],[0,-1]]
for i in range(n):
for j in range(n):
if g[i][j] == 0:
continue
for di in dirs:
x, y = i + di[0], j + di[1]
if x < 0 or x >= n or y < 0 or y >= n or g[x][y] == 0:
continue
self.union(p, sz, i * n + j + 1, x * n + y + 1)
for i in range(n):
for j in range(n):
if g[i][j] == 1:
ans = max(ans, sz[self.find(p, i * n + j + 1)])
else:
tot = 1
vis = set()
for di in dirs:
x, y = i + di[0], j + di[1]
if x < 0 or x >= n or y < 0 or y >= n or g[x][y] == 0:
continue
root = self.find(p, x * n + y + 1)
if root in vis:
continue
tot += sz[root]
vis.add(root)
ans = max(ans, tot)
return ans
- 時間複雜度：$O(n^2)$
- 空間複雜度：$O(n^2)$
最後
這是我們「刷穿 LeetCode」系列文章的第 No.827
篇，系列開始於 2021/01/01，截止於起始日 LeetCode 上共有 1916 道題目，部分是有鎖題，我們將先把所有不帶鎖的題目刷完。
在這個系列文章裏面，除了講解解題思路以外，還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應的代碼模板。
為了方便各位同學能夠電腦上進行調試和提交代碼，我建立了相關的倉庫： http://github.com/SharingSou... 。
在倉庫地址裏，你可以看到系列文章的題解鏈接、系列文章的相應代碼、LeetCode 原題鏈接和其他優選題解。
更多更全更熱門的「筆試/面試」相關資料可訪問排版精美的合集新基地 :tada::tada:
本文由mdnice多平台發佈
「其他文章」
- 天翼雲全場景業務無縫替換至國產原生操作系統CTyunOS！
- 以羊了個羊為例，淺談小程序抓包與響應報文修改
- 這幾種常見的 JVM 調優場景，你知道嗎？
- 如此狂妄，自稱高性能隊列的Disruptor有啥來頭？
- 為什麼要學習GoF設計模式？
- 827. 最大人工島 : 簡單「並查集 枚舉」運用題
- 手把手教你如何使用 Timestream 實現物聯網時序數據存儲和分析
- 850. 矩形面積 II : 掃描線模板題
- Java 併發編程解析 | 基於JDK源碼解析Java領域中的併發鎖，我們可以從中學習到什麼內容？
- 【手把手】光説不練假把式，這篇全鏈路壓測實踐探索
- 大廠鍾愛的全鏈路壓測有什麼意義？四種壓測方案詳細對比分析
- 寫個續集，填坑來了！關於“Thread.sleep(0)這一行‘看似無用’的代碼”裏面留下的坑。
- 857. 僱傭 K 名工人的最低成本 : 枚舉 優先隊列（堆）運用題
- Vue3 實現一個自定義toast（小彈窗）
- 669. 修剪二叉搜索樹 : 常規樹的遍歷與二叉樹性質
- 讀完 RocketMQ 源碼，我學會了如何優雅的創建線程
- 性能調優——小小的log大大的坑
- 1582. 二進制矩陣中的特殊位置 : 簡單模擬題
- elementui源碼學習之仿寫一個el-switch
- 646. 最長數對鏈 : 常規貪心 DP 運用題