奇怪的打印机 II
难度:
标签:
题目描述
给你一个奇怪的打印机，它有如下两个特殊的打印规则：
- 每一次操作时，打印机会用同一种颜色打印一个矩形的形状，每次打印会覆盖矩形对应格子里原本的颜色。
- 一旦矩形根据上面的规则使用了一种颜色，那么 相同的颜色不能再被使用 。
给你一个初始没有颜色的 m x n 的矩形 targetGrid ，其中 targetGrid[row][col] 是位置 (row, col) 的颜色。
如果你能按照上述规则打印出矩形 targetGrid ，请你返回 true ，否则返回 false 。
示例 1：
输入：targetGrid = [[1,1,1,1],[1,2,2,1],[1,2,2,1],[1,1,1,1]] 输出：true
示例 2：
输入：targetGrid = [[1,1,1,1],[1,1,3,3],[1,1,3,4],[5,5,1,4]] 输出：true
示例 3：
输入：targetGrid = [[1,2,1],[2,1,2],[1,2,1]] 输出：false 解释：没有办法得到 targetGrid ，因为每一轮操作使用的颜色互不相同。
示例 4：
输入：targetGrid = [[1,1,1],[3,1,3]] 输出：false
提示：
m == targetGrid.lengthn == targetGrid[i].length1 <= m, n <= 601 <= targetGrid[row][col] <= 60
代码结果
运行时间: 83 ms, 内存: 16.2 MB
// Solution in Java using Streams
// Approach: Similar to the Java solution, we use a map to track bounds for each color and then validate those bounds.
// However, we will use streams for data processing where possible.
import java.util.*;
import java.util.stream.*;
public class StrangePrinterStream {
public boolean isPrintable(int[][] targetGrid) {
int m = targetGrid.length;
int n = targetGrid[0].length;
Map<Integer, int[]> colorBounds = new HashMap<>();
// Determine bounds for each color using streams
IntStream.range(0, m).forEach(i ->
IntStream.range(0, n).forEach(j -> {
int color = targetGrid[i][j];
colorBounds.compute(color, (k, v) -> {
if (v == null) return new int[]{i, i, j, j};
v[0] = Math.min(v[0], i);
v[1] = Math.max(v[1], i);
v[2] = Math.min(v[2], j);
v[3] = Math.max(v[3], j);
return v;
});
})
);
// Verify if each color's rectangle is valid
return colorBounds.entrySet().stream().allMatch(entry -> {
int color = entry.getKey();
int[] bounds = entry.getValue();
return IntStream.range(bounds[0], bounds[1] + 1).allMatch(i ->
IntStream.range(bounds[2], bounds[3] + 1).allMatch(j ->
targetGrid[i][j] == color
)
);
});
}
public static void main(String[] args) {
StrangePrinterStream sp = new StrangePrinterStream();
int[][] targetGrid1 = {
{1, 1, 1, 1},
{1, 2, 2, 1},
{1, 2, 2, 1},
{1, 1, 1, 1}
};
System.out.println(sp.isPrintable(targetGrid1)); // true
int[][] targetGrid2 = {
{1, 1, 1, 1},
{1, 1, 3, 3},
{1, 1, 3, 4},
{5, 5, 1, 4}
};
System.out.println(sp.isPrintable(targetGrid2)); // true
int[][] targetGrid3 = {
{1, 2, 1},
{2, 1, 2},
{1, 2, 1}
};
System.out.println(sp.isPrintable(targetGrid3)); // false
}
}解释
方法:
此题解采用了模拟打印机打印过程的方法。首先，使用一个字典记录每种颜色最初和最终出现的行和列（形成一个边界框），这意味着如果颜色c在一个矩形区域内完整存在，则理论上可以通过一次打印操作实现该颜色。之后，对每个颜色尝试执行打印操作：检查其边界框内是否所有颜色都能匹配目标或已被覆盖（值为-1）。如果可以，那么该颜色对应的区域就被设置为-1以表示该区域已被完全打印覆盖。该过程反复进行，直到没有颜色可以成功打印（返回false）或所有颜色都被打印完（返回true）。
时间复杂度:
O(C * m * n)
空间复杂度:
O(C)
代码细节讲解
🦆
为什么在题解中使用字典来记录每种颜色的边界框而不是其他数据结构，如数组或列表？
▷🦆
在题解的打印检查函数`can_be_grid`中，为什么判断条件包括了`-1`？这代表了什么意义？
▷🦆
题解中提到，一旦可以打印某种颜色，就将该区域设置为-1。这样做有可能影响后续颜色的判断吗？如何避免或解决这种潜在问题？
▷🦆
在题解的逻辑中，如果在某一轮迭代中没有任何颜色被成功打印，就直接返回`false`。这种做法是否有可能漏掉某些特殊情况，导致错误的判断？
▷