2021-8-5

zhuchen · zhuchen · commit 0c388dc7ecc5 · 2021-08-05T22:56:26.000+08:00
diff --git a/question0827_making_a_large_island/Solution.java b/question0827_making_a_large_island/Solution.java
@@ -0,0 +1,101 @@
+package question0827_making_a_large_island;
+
+import java.util.HashSet;
+import java.util.Set;
+
+public class Solution {
+
+  private static class UnionFind {
+
+    int[] parent;
+
+    int n;
+
+    int setCount;
+
+    public UnionFind(int n) {
+      this.n = n;
+      this.parent = new int[n];
+      this.setCount = n;
+      for (int i = 0; i < n; ++i) {
+        parent[i] = i;
+      }
+    }
+
+    public int findParent(int x) {
+      int a = x;
+      while (x != parent[x]) {
+        x = parent[x];
+      }
+      while (a != parent[a]) {
+        int z = parent[a];
+        parent[a] = x;
+        a = z;
+      }
+      return x;
+    }
+
+    public boolean union(int a, int b) {
+      int aParent = findParent(a), bParent = findParent(b);
+      if (aParent != bParent) {
+        parent[aParent] = bParent;
+        setCount--;
+        return true;
+      }
+      return false;
+    }
+
+  }
+
+  public int largestIsland(int[][] grid) {
+    int n = grid.length;
+    UnionFind unionFind = new UnionFind(n * n);
+    int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
+    for (int i = 0; i < n; i++) {
+      for (int j = 0; j < n; j++) {
+        if (grid[i][j] == 1) {
+          for (int[] direction : directions) {
+            int nextI = i + direction[0], nextJ = j + direction[1];
+            if (nextI >= 0 && nextI < n && nextJ >= 0 && nextJ < n && grid[nextI][nextJ] == 1) {
+              unionFind.union(i * n + j, nextI * n + nextJ);
+            }
+          }
+        }
+      }
+    }
+    int[] count = new int[n * n];
+    for (int i = 0; i < unionFind.parent.length; i++) {
+      count[unionFind.findParent(i)]++;
+    }
+    int result = 0;
+    for (int i = 0; i < count.length; i++) {
+      result = Math.max(result, count[i]);
+    }
+    for (int i = 0; i < n; i++) {
+      for (int j = 0; j < n; j++) {
+        if (grid[i][j] == 0) {
+          int temp = 1;
+          Set<Integer> set = new HashSet<>();
+          for (int[] direction : directions) {
+            int nextI = i + direction[0], nextJ = j + direction[1];
+            if (nextI >= 0 && nextI < n && nextJ >= 0 && nextJ < n && grid[nextI][nextJ] == 1) {
+              int parent = unionFind.findParent(nextI * n + nextJ);
+              if (!set.contains(parent)) {
+                temp += count[parent];
+                set.add(parent);
+              }
+            }
+          }
+          result = Math.max(result, temp);
+        }
+      }
+    }
+    return result;
+  }
+
+  public static void main(String[] args) {
+    int[][] grid = {{1, 0}, {1, 1}};
+    System.out.println(new Solution().largestIsland(grid));
+  }
+
+}
