2023-05-11：给你一个 m x n 的二进制矩阵 grid，
每个格子要么为 0 （空）要么为 1 （被占据），
给你邮票的尺寸为 stampHeight x stampWidth。
我们想将邮票贴进二进制矩阵中，且满足以下 限制 和 要求 ：
覆盖所有空格子，不覆盖任何被占据的格子，
可以放入任意数目的邮票，邮票可以相互有重叠部分，
邮票不允许旋转，邮票必须完全在矩阵内，
如果在满足上述要求的前提下，可以放入邮票，请返回 true ，否则返回 false。
输入：grid = [[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0]], stampHeight = 4, stampWidth = 3。
输出：true。
答案2023-05-11：
大体过程如下：
1.首先对矩阵 grid 进行二维前缀和计算，得到一个新的矩阵 sum。该矩阵中每个位置表示从左上角出发，到该位置形成的子矩阵中所有元素的和。
2.对 grid 中的每个为 0 的位置 (i, j)，检查以该位置为左上角的子矩阵是否能够被指定的印章完全覆盖。如果可以，将 diff[i][j] 加 1，diff[i][j+stampWidth] 减 1，diff[i+stampHeight][j] 减 1，diff[i+stampHeight][j+stampWidth] 加 1。这里 diff 矩阵用于记录每个位置的变化量。
3.遍历 grid 中的每一行，使用滚动数组的方式还原 cnt 和 pre 数组，并通过它们来计算每列中为 0 的位置的数量。同时，如果某个位置 (i, j) 的值为 0 且它所在列中没有其他的 0，则返回 false；否则返回 true。
时间复杂度为 O(mn)，其中 m 和 n 分别表示矩阵 grid 的行数和列数。这是因为函数需要遍历整个矩阵，并对每个位置进行常数次操作。同时，二维前缀和、二维差分和滚动数组优化的时间复杂度也都是 O(mn)。
空间复杂度为 O(mn)，因为函数中创建了两个 m+1 行 n+1 列的二维数组 sum 和 diff，以及一个长度为 n+1 的一维数组 cnt 和 pre。这些数组所占用的总空间为 (m+1)(n+1) + 2(n+1) = mn + 3m + 3n + 3，即 O(mn)。
go完整代码如下：
package main
import "fmt"
func main() {
grid := [][]int{{1, 0, 0, 0}, {1, 0, 0, 0}, {1, 0, 0, 0}, {1, 0, 0, 0}, {1, 0, 0, 0}}
stampHeight := 4
stampWidth := 3
isPossibleToStamp := possibleToStamp(grid, stampHeight, stampWidth)
fmt.Println(isPossibleToStamp)
}
func possibleToStamp(grid [][]int, stampHeight, stampWidth int) bool {
m, n := len(grid), len(grid[0])
sum := make([][]int, m+1)
sum[0] = make([]int, n+1)
diff := make([][]int, m+1)
diff[0] = make([]int, n+1)
for i, row := range grid {
sum[i+1] = make([]int, n+1)
for j, v := range row { // grid 的二维前缀和
sum[i+1][j+1] = sum[i+1][j] + sum[i][j+1] - sum[i][j] + v
}
diff[i+1] = make([]int, n+1)
}
for i, row := range grid {
for j, v := range row {
if v == 0 {
x, y := i+stampHeight, j+stampWidth // 注意这是矩形右下角横纵坐标都 +1 后的位置
if x 
rust完整代码如下：
fn main() {
let grid = vec![
vec![1, 0, 0, 0],
vec![1, 0, 0, 0],
vec![1, 0, 0, 0],
vec![1, 0, 0, 0],
vec![1, 0, 0, 0],
];
let stamp_height = 4;
let stamp_width = 3;
let is_possible_to_stamp = possible_to_stamp(&grid, stamp_height, stamp_width);
println!("{}", is_possible_to_stamp);
}
fn possible_to_stamp(grid: &[Vec], stamp_height: usize, stamp_width: usize) -> bool {
let m = grid.len();
let n = grid[0].len();
let mut sum = vec![vec![0; n + 1]; m + 1];
let mut diff = vec![vec![0; n + 1]; m + 1];
for i in 0..m {
for j in 0..n {
sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + grid[i][j];
}
}
for i in 0..m {
for j in 0..n {
if grid[i][j] == 0 {
let x = i + stamp_height;
let y = j + stamp_width;
if x 
c语言完整代码如下：
#include
#include
int possibleToStamp(int** grid, int gridSize, int* gridColSize, int stampHeight, int stampWidth) {
int m = gridSize, n = *gridColSize;
int** sum = (int**)malloc(sizeof(int*) * (m + 1));
for (int i = 0; i 
c++完整代码如下：
#include
#include
using namespace std;
bool possibleToStamp(vector>& grid, int stampHeight, int stampWidth) {
int m = grid.size(), n = grid[0].size();
vector> sum(m + 1, vector(n + 1)), diff(m + 1, vector(n + 1));
for (int i = 0; i cnt(n + 1), pre(n + 1);
for (int i = 0; i > grid{ {1, 0, 0, 0}, {1, 0, 0, 0}, {1, 0, 0, 0}, {1, 0, 0, 0}, {1, 0, 0, 0} };
int stampHeight = 4, stampWidth = 3;
bool isPossibleToStamp = possibleToStamp(grid, stampHeight, stampWidth);
cout 
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.e1idc.net
