写点什么

2023-05-11:给你一个 m x n 的二进制矩阵 grid, 每个格子要么为 0 (空)要么为 1 (被占据), 给你邮票的尺寸为 stampHeight x stampWidth。 我们想将

  • 2023-05-11
    北京
  • 本文字数:4476 字

    阅读完需:约 15 分钟

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 中的每一行,使用滚动数组的方式还原 cntpre 数组,并通过它们来计算每列中为 0 的位置的数量。同时,如果某个位置 (i, j) 的值为 0 且它所在列中没有其他的 0,则返回 false;否则返回 true。


时间复杂度为 O(mn),其中 m 和 n 分别表示矩阵 grid 的行数和列数。这是因为函数需要遍历整个矩阵,并对每个位置进行常数次操作。同时,二维前缀和、二维差分和滚动数组优化的时间复杂度也都是 O(mn)。


空间复杂度为 O(mn),因为函数中创建了两个 m+1 行 n+1 列的二维数组 sumdiff,以及一个长度为 n+1 的一维数组 cntpre。这些数组所占用的总空间为 (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 <= m && y <= n && sum[x][y]-sum[x][j]-sum[i][y]+sum[i][j] == 0 { diff[i][j]++ diff[i][y]-- diff[x][j]-- diff[x][y]++ // 更新二维差分 } } } }
// 还原二维差分矩阵对应的计数矩阵,这里用滚动数组实现 cnt := make([]int, n+1) pre := make([]int, n+1) for i, row := range grid { for j, v := range row { cnt[j+1] = cnt[j] + pre[j+1] - pre[j] + diff[i][j] if cnt[j+1] == 0 && v == 0 { return false } } cnt, pre = pre, cnt } return true}
复制代码


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<i32>], 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 <= m && y <= n && sum[x][y] - sum[x][j] - sum[i][y] + sum[i][j] == 0 { diff[i][j] += 1; diff[i][y] -= 1; diff[x][j] -= 1; diff[x][y] += 1; } } } }
let mut cnt = vec![0; n + 1]; let mut pre = vec![0; n + 1];
for i in 0..m { for j in 0..n { cnt[j + 1] = cnt[j] + pre[j + 1] - pre[j] + diff[i][j];
if cnt[j + 1] == 0 && grid[i][j] == 0 { return false; } }
std::mem::swap(&mut cnt, &mut pre); }
true}
复制代码


c 语言完整代码如下:

#include <stdio.h>#include <stdlib.h>
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 <= m; i++) { sum[i] = (int*)malloc(sizeof(int) * (n + 1)); } int** diff = (int**)malloc(sizeof(int*) * (m + 1)); for (int i = 0; i <= m; i++) { diff[i] = (int*)malloc(sizeof(int) * (n + 1)); }
for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + grid[i][j]; } }
for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 0) { int x = i + stampHeight, y = j + stampWidth; if (x <= m && y <= n && sum[x][y] - sum[x][j] - sum[i][y] + sum[i][j] == 0) { diff[i][j]++; diff[i][y]--; diff[x][j]--; diff[x][y]++; } } } }
int* cnt = (int*)malloc(sizeof(int) * (n + 1)); int* pre = (int*)malloc(sizeof(int) * (n + 1)); for (int i = 0; i <= n; i++) { cnt[i] = 0; pre[i] = 0; } for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { cnt[j + 1] = cnt[j] + pre[j + 1] - pre[j] + diff[i][j]; if (cnt[j + 1] == 0 && grid[i][j] == 0) { free(cnt); free(pre); for (int k = 0; k <= m; k++) { free(sum[k]); } free(sum); for (int k = 0; k <= m; k++) { free(diff[k]); } free(diff); return 0; } } int* tmp = cnt; cnt = pre; pre = tmp; }
free(cnt); free(pre); for (int i = 0; i <= m; i++) { free(sum[i]); } free(sum); for (int i = 0; i <= m; i++) { free(diff[i]); } free(diff); return 1;}
int main() { int gridSize = 5, gridColSize = 4; int** grid = (int**)malloc(sizeof(int*) * gridSize); for (int i = 0; i < gridSize; i++) { grid[i] = (int*)malloc(sizeof(int) * gridColSize); } int data[5][4] = { {1, 0, 0, 0}, {1, 0, 0, 0}, {1, 0, 0, 0}, {1, 0, 0, 0}, {1, 0, 0, 0} }; for (int i = 0; i < gridSize; i++) { for (int j = 0; j < gridColSize; j++) { grid[i][j] = data[i][j]; } } int stampHeight = 4, stampWidth = 3; int isPossibleToStamp = possibleToStamp(grid, gridSize, &gridColSize, stampHeight, stampWidth); printf("%s\n", isPossibleToStamp ? "true" : "false"); for (int i = 0; i < gridSize; i++) { free(grid[i]); } free(grid); return 0;}
复制代码


c++完整代码如下:

#include <iostream>#include <vector>
using namespace std;
bool possibleToStamp(vector<vector<int>>& grid, int stampHeight, int stampWidth) { int m = grid.size(), n = grid[0].size(); vector<vector<int>> sum(m + 1, vector<int>(n + 1)), diff(m + 1, vector<int>(n + 1));
for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + grid[i][j]; } }
for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 0) { int x = i + stampHeight, y = j + stampWidth; if (x <= m && y <= n && sum[x][y] - sum[x][j] - sum[i][y] + sum[i][j] == 0) { diff[i][j]++; diff[i][y]--; diff[x][j]--; diff[x][y]++; } } } }
vector<int> cnt(n + 1), pre(n + 1); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { cnt[j + 1] = cnt[j] + pre[j + 1] - pre[j] + diff[i][j]; if (cnt[j + 1] == 0 && grid[i][j] == 0) { return false; } } swap(cnt, pre); }
return true;}
int main() { vector<vector<int>> 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 << (isPossibleToStamp ? "true" : "false") << endl; return 0;}
复制代码



发布于: 刚刚阅读数: 3
用户头像

公众号:福大大架构师每日一题 2021-02-15 加入

公众号:福大大架构师每日一题

评论

发布
暂无评论
2023-05-11:给你一个 m x n 的二进制矩阵 grid, 每个格子要么为 0 (空)要么为 1 (被占据), 给你邮票的尺寸为 stampHeight x stampWidth。 我们想将_Go_福大大架构师每日一题_InfoQ写作社区