Medium

题目描述

有一个 n x n 的 0 索引网格，其中埋藏着一些文物。给你整数 n 和一个 0 索引二维整数数组 artifacts，用来描述矩形文物的位置，其中 artifacts[i] = [r1i, c1i, r2i, c2i] 表示第 i 个文物埋藏在子网格中：

  • (r1i, c1i) 是第 i 个文物的左上角单元格的坐标
  • (r2i, c2i) 是第 i 个文物的右下角单元格的坐标

你将会挖掘网格中的一些单元格并清除其中的泥土。如果单元格中埋有文物的一部分，那么该文物就会被发现。如果一个文物的所有部分都被发现，你就可以提取该文物。

给你一个 0 索引二维整数数组 dig，其中 dig[i] = [ri, ci] 表示你将会挖掘单元格 (ri, ci)，请你返回你可以提取的文物数量。

测试用例保证：

  • 没有两个文物重叠
  • 每个文物最多覆盖 4 个单元格
  • dig 中的条目都是唯一的

示例 1：

输入：n = 2, artifacts = [[0,0,0,0],[0,1,1,1]], dig = [[0,0],[0,1]]
输出：1
解释：不同颜色代表不同的文物。挖掘的单元格用网格中的 'D' 标记。
有 1 个文物可以提取，即红色文物。
蓝色文物在单元格 (1,1) 有一部分未被发现，所以我们无法提取它。
因此，返回 1。

示例 2：

输入：n = 2, artifacts = [[0,0,0,0],[0,1,1,1]], dig = [[0,0],[0,1],[1,1]]
输出：2
解释：红色和蓝色文物的所有部分都被发现（标记为 'D'）并且可以提取，所以返回 2。

提示：

  • 1 <= n <= 1000
  • 1 <= artifacts.length, dig.length <= min(n², 10⁵)
  • artifacts[i].length == 4
  • dig[i].length == 2
  • 0 <= r1i, c1i, r2i, c2i, ri, ci <= n - 1
  • r1i <= r2i
  • c1i <= c2i
  • 没有两个文物重叠
  • 每个文物覆盖的单元格数最多为 4
  • dig 中的条目都是唯一的

解题思路

这道题的核心思路是模拟挖掘过程，判断每个文物是否完全被挖掘出来。

解题思路：

  1. 标记挖掘位置：首先遍历所有挖掘位置，用哈希集合或二维数组标记哪些位置被挖掘了。这样可以在 O(1) 时间内查询某个位置是否被挖掘。

  2. 检查文物状态：对于每个文物，遍历它覆盖的所有单元格，检查是否都被挖掘了。文物的覆盖范围是从 (r1, c1) 到 (r2, c2) 的矩形区域。

  3. 计数完全挖掘的文物：如果一个文物的所有单元格都被挖掘，则计数器加一。

优化考虑：

  • 使用哈希集合存储挖掘位置比二维数组更节省空间，因为挖掘位置可能稀疏
  • 题目限制每个文物最多覆盖 4 个单元格，所以内层循环复杂度很小

时间复杂度分析：

  • 构建挖掘位置集合：O(dig.length)
  • 检查所有文物：O(artifacts.length × 4) = O(artifacts.length)
  • 总时间复杂度：O(dig.length + artifacts.length)

代码实现

class Solution {
public:
    int digArtifacts(int n, vector<vector<int>>& artifacts, vector<vector<int>>& dig) {
        // 使用set存储已挖掘的位置
        set<pair<int, int>> excavated;
        for (auto& d : dig) {
            excavated.insert({d[0], d[1]});
        }
        
        int count = 0;
        // 检查每个文物是否完全被挖掘
        for (auto& artifact : artifacts) {
            int r1 = artifact[0], c1 = artifact[1];
            int r2 = artifact[2], c2 = artifact[3];
            
            bool canExtract = true;
            // 检查文物覆盖的所有单元格
            for (int r = r1; r <= r2; r++) {
                for (int c = c1; c <= c2; c++) {
                    if (excavated.find({r, c}) == excavated.end()) {
                        canExtract = false;
                        break;
                    }
                }
                if (!canExtract) break;
            }
            
            if (canExtract) count++;
        }
        
        return count;
    }
};

class Solution:
    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:
        # 使用set存储已挖掘的位置
        excavated = set((r, c) for r, c in dig)
        
        count = 0
        # 检查每个文物是否完全被挖掘
        for r1, c1, r2, c2 in artifacts:
            can_extract = True
            # 检查文物覆盖的所有单元格
            for r in range(r1, r2 + 1):
                for c in range(c1, c2 + 1):
                    if (r, c) not in excavated:
                        can_extract = False
                        break
                if not can_extract:
                    break
            
            if can_extract:
                count += 1
        
        return count

public class Solution {
    public int DigArtifacts(int n, int[][] artifacts, int[][] dig) {
        // 使用HashSet存储已挖掘的位置
        HashSet<(int, int)> excavated = new HashSet<(int, int)>();
        foreach (int[] d in dig) {
            excavated.Add((d[0], d[1]));
        }
        
        int count = 0;
        // 检查每个文物是否完全被挖掘
        foreach (int[] artifact in artifacts) {
            int r1 = artifact[0], c1 = artifact[1];
            int r2 = artifact[2], c2 = artifact[3];
            
            bool canExtract = true;
            // 检查文物覆盖的所有单元格
            for (int r = r1; r <= r2; r++) {
                for (int c = c1; c <= c2; c++) {
                    if (!excavated.Contains((r, c))) {
                        canExtract = false;
                        break;
                    }
                }
                if (!canExtract) break;
            }
            
            if (canExtract) count++;
        }
        
        return count;
    }
}

var digArtifacts = function(n, artifacts, dig) {
    // 使用Set存储已挖掘的位置
    const excavated = new Set();
    for (let [r, c] of dig) {
        excavated.add(`${r},${c}`);
    }
    
    let count = 0;
    // 检查每个文物是否完全被挖掘
    for (let [r1, c1, r2, c2] of artifacts) {
        let canExtract = true;
        // 检查文物覆盖的所有单元格
        for (let r = r1; r <= r2; r++) {
            for (let c = c1; c <= c2; c++) {
                if (!excavated.has(`${r},${c}`)) {
                    canExtract = false;
                    break;
                }
            }
            if (!canExtract) break;
        }
        
        if (canExtract) count++;
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(D + A)D 为挖掘位置数量，A 为文物数量，每个文物最多检查 4 个单元格
空间复杂度O(D)存储挖掘位置的哈希集合

相关题目