一，题目

二，分析

三，解法

四，参考

leetcode网站的题解参考

Union Find的一种别样实现（解释rank）

  1. class Solution {
  2.     public int[] hitBricks(int[][] grid, int[][] hits) {
  3.         int R = grid.length, C = grid[0].length;
  4.         int[] dr = {1, 0, -1, 0};
  5.         int[] dc = {0, 1, 0, -1};
  7.         int[][] A = new int[R][C];
  8.         for (int r = 0; r < R; ++r)
  9.             A[r] = grid[r].clone();
  10.         for (int[] hit: hits)
  11.             A[hit[0]][hit[1]] = 0;
  13.         DSU dsu = new DSU(R*C + 1);
  14.         for (int r = 0; r < R; ++r) {
  15.             for (int c = 0; c < C; ++c) {
  16.                 if (A[r][c] == 1) {
  17.                     int i = r * C + c;
  18.                     if (r == 0)
  19.                         dsu.union(i, R*C);
  20.                     if (r > 0 && A[r-1][c] == 1)
  21.                         dsu.union(i, (r-1) *C + c);
  22.                     if (c > 0 && A[r][c-1] == 1)
  23.                         dsu.union(i, r * C + c-1);
  24.                 }
  25.             }
  26.         }
  27.         int t = hits.length;
  28.         int[] ans = new int[t--];
  30.         while (t >= 0) {
  31.             int r = hits[t][0];
  32.             int c = hits[t][1];
  33.             int preRoof = dsu.top();
  34.             if (grid[r][c] == 0) {
  35.                 t--;
  36.             } else {
  37.                 int i = r * C + c;
  38.                 for (int k = 0; k < 4; ++k) {
  39.                     int nr = r + dr[k];
  40.                     int nc = c + dc[k];
  41.                     if (0 <= nr && nr < R && 0 <= nc && nc < C && A[nr][nc] == 1)
  42.                         dsu.union(i, nr * C + nc);
  43.                 }
  44.                 if (r == 0)
  45.                     dsu.union(i, R*C);
  46.                 A[r][c] = 1;
  47.                 ans[t--] = Math.max(0, dsu.top() - preRoof - 1);
  48.             }
  49.         }
  51.         return ans;
  52.     }
  53. }
  55. class DSU {
  56.     int[] parent;
  57.     int[] rank;
  58.     int[] sz;
  60.     public DSU(int N) {
  61.         parent = new int[N];
  62.         for (int i = 0; i < N; ++i)
  63.             parent[i] = i;
  64.         rank = new int[N];
  65.         sz = new int[N];
  66.         Arrays.fill(sz, 1);
  67.     }
  69.       //这里采用了路径压缩，在搜索的时候把所有经过的节点的parent都指向了根节点
  70.     public int find(int x) {
  71.         if (parent[x] != x) parent[x] = find(parent[x]);
  72.         return parent[x];
  73.     }
  75.     public void union(int x, int y) {
  76.         int xr = find(x), yr = find(y);
  77.         if (xr == yr) return;
  79.                 //这里的交换操作使得yr永远是是权重(rank)小的那个
  80.         if (rank[xr] < rank[yr]) {
  81.             int tmp = yr;
  82.             yr = xr;
  83.             xr = tmp;
  84.         }
  85.         if (rank[xr] == rank[yr])
  86.             rank[xr]++;
  87.                 //yr是权重(rank)小的那个
  88.         parent[yr] = xr;
  89.         sz[xr] += sz[yr];
  90.     }
  92.     public int size(int x) {
  93.         return sz[find(x)];
  94.     }
  96.     public int top() {
  97.         return size(sz.length - 1) - 1;
  98.     }
  99. }