统计可以提取的工件

难度:

标签:

题目描述

存在一个 n x n 大小、下标从 0 开始的网格，网格中埋着一些工件。给你一个整数 n 和一个下标从 0 开始的二维整数数组 artifacts ，artifacts 描述了矩形工件的位置，其中 artifacts[i] = [r1_i, c1_i, r2_i, c2_i] 表示第 i 个工件在子网格中的填埋情况：

(r1_i, c1_i) 是第 i 个工件左上单元格的坐标，且
(r2_i, c2_i) 是第 i 个工件右下单元格的坐标。

你将会挖掘网格中的一些单元格，并清除其中的填埋物。如果单元格中埋着工件的一部分，那么该工件这一部分将会裸露出来。如果一个工件的所有部分都都裸露出来，你就可以提取该工件。

给你一个下标从 0 开始的二维整数数组 dig ，其中 dig[i] = [r_i, c_i] 表示你将会挖掘单元格 (r_i, c_i) ，返回你可以提取的工件数目。

生成的测试用例满足：

不存在重叠的两个工件。
每个工件最多只覆盖 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 <= r1_i, c1_i, r2_i, c2_i, r_i, c_i <= n - 1
r1_i <= r2_i
c1_i <= c2_i
不存在重叠的两个工件
每个工件最多只覆盖 4 个单元格
dig 中的元素互不相同

代码结果

运行时间: 156 ms, 内存: 57.3 MB

// 思路：
// 1. 使用Java Stream API来优化流程。
// 2. 初始化网格并标记已挖掘的点。
// 3. 使用stream和lambda表达式检查每个工件是否可以提取。

import java.util.Set;
import java.util.HashSet;
import java.util.Arrays;

public class ArtifactExtractionStream {
    public int countExtractableArtifacts(int n, int[][] artifacts, int[][] dig) {
        Set<String> digSet = new HashSet<>();
        Arrays.stream(dig).forEach(d -> digSet.add(d[0] + "," + d[1]));
        return (int) Arrays.stream(artifacts).filter(artifact -> {
            for (int i = artifact[0]; i <= artifact[2]; i++) {
                for (int j = artifact[1]; j <= artifact[3]; j++) {
                    if (!digSet.contains(i + "," + j)) return false;
                }
            }
            return true;
        }).count();
    }
}

解释

方法:

这个题解首先通过构建一个二维数组 `vis` 来记录所有被挖掘的单元格，其中 `vis[i][j]` 为 1 表示单元格 `(i, j)` 已经被挖掘。接着，对每一个工件，检查其对应的矩形区域内的所有单元格是否都已被挖掘（即检查这些单元格在 `vis` 中的值是否都为 1）。如果一个工件的所有部分都被挖掘了，那么这个工件可以被提取，计数器 `ans` 加一。最后，返回可以提取的工件数量。

时间复杂度:

O(L + A*4)

空间复杂度:

O(n^2)

代码细节讲解

🦆

在题解中，为什么选择使用二维数组`vis`来标记挖掘的单元格，而不是其他数据结构如哈希表？

▷

在题解中选择使用二维数组`vis`而不是哈希表的主要原因是空间和时间效率。二维数组允许直接通过索引访问元素，这在本题中特别适用，因为需要频繁地检查每个单元格是否被挖掘。使用二维数组可以以 O(1) 的时间复杂度直接访问任何位置，而不需要额外的哈希计算，这样可以减少运算时间。此外，由于`n x n`的网格大小是预先确定的，使用二维数组可以直观地表示每个单元格的状态，而使用哈希表可能会增加不必要的内存开销和查找成本。

🦆

在实现中，如果`dig`数组中存在重复的挖掘坐标，这会对算法产生什么影响？是否需要对此进行处理？

▷

在实现中，如果`dig`数组中存在重复的挖掘坐标，实际上不会对算法的最终结果产生影响。这是因为即使一个单元格被重复标记为已挖掘（即`vis[a][b]`被多次设置为1），它仍然只计算为一个挖掘过的单元格。因此，这种重复不会错误地增加已挖掘工件的数量。由于这种重复不影响最终结果，不需要在算法中特别处理这一情况。

🦆

题解假设不存在重叠的工件，如果这一假设改变，目前的算法需要如何调整以应对可能的重叠？

▷

如果工件之间允许存在重叠，当前的算法需要调整以正确统计可提取的工件数量。具体来说，可以实施以下策略：为每个工件分配一个独立的计数器，记录其被完全挖掘的单元格数量。在遍历`dig`数组时，不仅将挖掘的单元格在`vis`中标记为1，同时更新所有包含该单元格的工件的计数器。每个工件的计数器需要达到其所覆盖的单元格总数才能被认为是完全挖掘的。这种方法需要额外的数据结构来跟踪每个工件的挖掘进度，并可能需要更复杂的逻辑来管理工件之间的重叠。

统计可以提取的工件

题目描述

代码结果

解释

代码细节讲解

相关问题