Re: [閒聊] 每日leetcode
※ 引述 《enmeitiryous (enmeitiryous)》 之銘言：
:
: 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才進行檢查。
: 結果比暴力法遍歷慢 唉
:
思路:
暴力暴力暴力暴力
多寫一個函式跑判定
用紀錄的
如果這個matrix大一點
搞不好就要在原本grid裡面用到prefix sum?
姆咪
```cpp
class Solution {
public:
bool ok(vector<vector<int>>& grid , int i , int j)
{
vector<int> num(16,0);
vector<int> rs(3,0);
vector<int> cs(3,0);
for(int k = i-1 ; k <= i+1 ; k ++)
{
for(int p = j-1 ; p <= j+1 ; p ++)
{
num[grid[k][p]]++;
rs[k+1-i]+=grid[k][p];
cs[p+1-j]+=grid[k][p];
}
}
for(int p = 1 ; p <= 9 ; p ++)
{
if(!num[p])return false;
}
for(int p = 0 ; p < 2; p ++)
{
if(rs[p]!=rs[p+1])return false;
if(cs[p]!=cs[p+1])return false;
}
if(cs[0]!=rs[0])return false;
if(grid[i-1][j-1] + grid[i+1][j+1] != grid[i+1][j-1]+grid[i-1][j+1])retu
rn false;
return true;
}
int numMagicSquaresInside(vector<vector<int>>& grid)
{
int res = 0;
int n = grid.size();
int m = grid[0].size();
for(int i = 1 ; i < n-1 ; i ++)
{
for(int j = 1 ; j < m-1 ; j ++)
{
if(ok(grid,i,j))res++;
}
}
return res;
}
};
```
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.10.12.220 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1723169414.A.81B.html
→
08/09 10:17,
1年前
, 1F
08/09 10:17, 1F
推
08/09 10:21,
1年前
, 2F
08/09 10:21, 2F
討論串 (同標題文章)