Re: [閒聊] 每日leetcode
看板Marginalman作者enmeitiryous (enmeitiryous)時間1年前 (2024/08/09 09:41)推噓0(0推 0噓 1→)留言1則, 1人參與討論串676/1548 (看更多)
840. Magic Squares In Grid
題目:
給你一個matrix grid:其中0<=grid[i][j]<=15，求grid中有多少個3*3submatrix符合
magic square的定義
思路:
有興趣可以看一下magic sqaure的維基，可以知道不論怎麼填3*3的magic square的中心
值一定會是5，且row sum必是15，就按照magic square的定義寫一個額外func來確定給定
的方陣是不是magic square，且只在遍歷原matrix時遇到不在邊界上的5才進行檢查。
結果比暴力法遍歷慢 唉
bool he_pler(vector<vector<int>> &grid, int i, int j){
unordered_set<int> gg;
for(int y=i-1;y<i+2;++y){
for(int x=j-1;x<j+2;++x){
if(grid[y][x]>9 || grid[y][x]<1){
return false;
}
gg.insert(grid[y][x]);
}
}
if(gg.size()<9){
return false;
}
if(grid[i][j]+grid[i][j+1]+grid[i][j-1]!=15){
return false;
}
if(grid[i+1][j]+grid[i+1][j+1]+grid[i+1][j-1]!=15){
return false;
}
if(grid[i-1][j]+grid[i-1][j+1]+grid[i-1][j-1]!=15){
return false;
}
if(grid[i+1][j]+grid[i][j]+grid[i-1][j]!=15){
return false;
}
if(grid[i+1][j-1]+grid[i][j-1]+grid[i-1][j-1]!=15){
return false;
}
if(grid[i+1][j+1]+grid[i][j+1]+grid[i-1][j+1]!=15){
return false;
}
if(grid[i-1][j-1]+grid[i][j]+grid[i+1][j+1]!=15){
return false;
}
if(grid[i-1][j+1]+grid[i][j]+grid[i+1][j-1]!=15){
return false;
}
return true;
}
int numMagicSquaresInside(vector<vector<int>>& grid) {
if(grid.size()<3 || grid[0].size()<3){
return 0;
}
int m=grid.size();
int n=grid[0].size();
int ans=0;
for(int i=0;i<m;++i){
for(int j=0;j<n;++j){
if(grid[i][j]==5 &&i>0 &&i<m-1 && j>0 && j<n-1){
if(he_pler(grid,i,j)){
ans++;
}
}
}
}
return ans;
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.227.239.43 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1723167682.A.F46.html
→
08/09 10:27,
1年前
, 1F
08/09 10:27, 1F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 676 之 1548 篇)：