2023-05-11：給你一個(gè) m x n 的二進(jìn)制矩陣 grid， 每個(gè)格子要么為 0 （空）要么為 1
2023-05-11：給你一個(gè) m x n 的二進(jìn)制矩陣 grid，
每個(gè)格子要么為 0 （空）要么為 1 （被占據(jù)），
給你郵票的尺寸為 stampHeight x stampWidth。
我們想將郵票貼進(jìn)二進(jìn)制矩陣中，且滿(mǎn)足以下 限制 和 要求 ：
覆蓋所有空格子，不覆蓋任何被占據(jù)的格子，
可以放入任意數(shù)目的郵票，郵票可以相互有重疊部分，
郵票不允許旋轉(zhuǎn)，郵票必須完全在矩陣內(nèi)，
如果在滿(mǎn)足上述要求的前提下，可以放入郵票，請(qǐng)返回 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：
大體過(guò)程如下：
1.首先對(duì)矩陣?grid?進(jìn)行二維前綴和計(jì)算，得到一個(gè)新的矩陣?sum。該矩陣中每個(gè)位置表示從左上角出發(fā)，到該位置形成的子矩陣中所有元素的和。
2.對(duì)?grid?中的每個(gè)為 0 的位置?(i, j)，檢查以該位置為左上角的子矩陣是否能夠被指定的印章完全覆蓋。如果可以，將?diff[i][j]?加 1，diff[i][j+stampWidth]?減 1，diff[i+stampHeight][j]?減 1，diff[i+stampHeight][j+stampWidth]?加 1。這里?diff?矩陣用于記錄每個(gè)位置的變化量。
3.遍歷?grid?中的每一行，使用滾動(dòng)數(shù)組的方式還原?cnt?和?pre?數(shù)組，并通過(guò)它們來(lái)計(jì)算每列中為 0 的位置的數(shù)量。同時(shí)，如果某個(gè)位置?(i, j)?的值為 0 且它所在列中沒(méi)有其他的 0，則返回 false；否則返回 true。
時(shí)間復(fù)雜度為 O(mn)，其中 m 和 n 分別表示矩陣?grid?的行數(shù)和列數(shù)。這是因?yàn)楹瘮?shù)需要遍歷整個(gè)矩陣，并對(duì)每個(gè)位置進(jìn)行常數(shù)次操作。同時(shí)，二維前綴和、二維差分和滾動(dòng)數(shù)組優(yōu)化的時(shí)間復(fù)雜度也都是 O(mn)。
空間復(fù)雜度為 O(mn)，因?yàn)楹瘮?shù)中創(chuàng)建了兩個(gè) m+1 行 n+1 列的二維數(shù)組?sum?和?diff，以及一個(gè)長(zhǎng)度為 n+1 的一維數(shù)組?cnt?和?pre。這些數(shù)組所占用的總空間為 (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?//?注意這是矩形右下角橫縱坐標(biāo)都?+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]++?//?更新二維差分
????????????????}
????????????}
????????}
????}
????//?還原二維差分矩陣對(duì)應(yīng)的計(jì)數(shù)矩陣，這里用滾動(dòng)數(shù)組實(shí)現(xiàn)
????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語(yǔ)言完整代碼如下：
#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;
}
福大大架構(gòu)師每日一題
java當(dāng)死，golang當(dāng)立。最新面試題，涉及golang，rust，mysql，redis，云原生，算法，分布式，網(wǎng)絡(luò)，操作系統(tǒng)。
公眾號(hào)
