元宝DeepSeek深度思考 LeetCode 803.打砖块 public int[] hitBricks(int[][] grid, int[][] hits)

LeetCode 803. 打砖块问题可以通过逆向思维结合并查集高效解决。核心思路是：先将所有被敲击的砖块移除，然后从最后一次敲击开始逆向添加砖块，并利用并查集维护与顶部相连的砖块数量。每次添加砖块时，计算有多少砖块因该操作重新与顶部连接，其数量减1即为正向敲击时掉落的砖块数。

稚辉君.MCA.P9.JAVA

537人浏览 · 2026-03-23 01:25:46

稚辉君.MCA.P9.JAVA · 2026-03-23 01:25:46 发布

以下是完整的Java实现：

class Solution {
private int rows;
private int cols;
public static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};

public int[] hitBricks(int[][] grid, int[][] hits) {
    this.rows = grid.length;
    this.cols = grid[0].length;
    
    // 复制网格，避免修改原数组
    int[][] copy = new int[rows][cols];
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            copy[i][j] = grid[i][j];
        }
    }
    
    // 预先敲掉所有会被击中的砖块
    for (int[] hit : hits) {
        if (copy[hit[0]][hit[1]] == 1) {
            copy[hit[0]][hit[1]] = 0;
        }
    }
    
    // 并查集初始化，多出的一个节点代表“屋顶”
    int size = rows * cols;
    UnionFind unionFind = new UnionFind(size + 1);
    
    // 将第一行的砖块与“屋顶”相连
    for (int j = 0; j < cols; j++) {
        if (copy[0][j] == 1) {
            unionFind.union(j, size);
        }
    }
    
    // 连接剩余的砖块
    for (int i = 1; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (copy[i][j] == 1) {
                // 如果上方也是砖块，连接
                if (copy[i - 1][j] == 1) {
                    unionFind.union(getIndex(i - 1, j), getIndex(i, j));
                }
                // 如果左边也是砖块，连接
                if (j > 0 && copy[i][j - 1] == 1) {
                    unionFind.union(getIndex(i, j - 1), getIndex(i, j));
                }
            }
        }
    }
    
    // 逆序遍历敲击操作
    int hitsLen = hits.length;
    int[] res = new int[hitsLen];
    for (int i = hitsLen - 1; i >= 0; i--) {
        int x = hits[i][0];
        int y = hits[i][1];
        
        // 如果原位置没有砖块，则无砖块掉落
        if (grid[x][y] == 0) {
            continue;
        }
        
        // 记录添加当前砖块前，与屋顶相连的砖块数
        int origin = unionFind.getSize(size);
        
        // 如果当前砖块在第一行，将其与屋顶相连
        if (x == 0) {
            unionFind.union(y, size);
        }
        
        // 遍历四个方向，合并相邻砖块
        for (int[] direction : DIRECTIONS) {
            int newX = x + direction[0];
            int newY = y + direction[1];
            if (inArea(newX, newY) && copy[newX][newY] == 1) {
                unionFind.union(getIndex(x, y), getIndex(newX, newY));
            }
        }
        
        // 记录添加当前砖块后，与屋顶相连的砖块数
        int current = unionFind.getSize(size);
        // 由于屋顶节点本身不计入，所以实际砖块数为当前值减1
        // 新连接的砖块数 = (current - 1) - (origin - 1) = current - origin
        // 掉落砖块数 = 新连接的砖块数 - 1（当前砖块本身不计入掉落）
        res[i] = Math.max(0, current - origin - 1);
        
        // 将当前砖块标记回原位
        copy[x][y] = 1;
    }
    return res;
}

// 将二维坐标映射为一维索引
private int getIndex(int x, int y) {
    return x * cols + y;
}

// 检查坐标是否在网格内
private boolean inArea(int x, int y) {
    return x >= 0 && x < rows && y >= 0 && y < cols;
}

// 并查集类
private class UnionFind {
    private int[] parent;
    private int[] size;
    
    public UnionFind(int n) {
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }
    
    // 路径压缩查找根节点
    public int find(int x) {
        if (x != parent[x]) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    // 按秩合并
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) {
            return;
        }
        parent[rootX] = rootY;
        size[rootY] += size[rootX];
    }
    
    // 获取根节点所在连通分量的大小
    public int getSize(int x) {
        int root = find(x);
        return size[root];
    }
}

}

算法关键点：