Re: [閒聊] 每日leetcode
※ 引述《oin1104 (是oin的說)》之銘言：
: ※ 引述 《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才進行檢查。
: : 結果比暴力法遍歷慢 唉
思路 暴力法 走過每一個3x3左上點
先寫一個func檢查中心==5, 每格是不是數值在1-9
再寫一個func檢查row sum, col sum, diagonal sum == 15
都是就把答案+1
class Solution {
public:
int isNumsValid(vector<vector<int>>& grid, int i, int j){
vector<int> valid(9);
if(grid[i+1][j+1] != 5) return false;
for(int r = 0; r < 3; ++r){
for(int c = 0; c < 3; ++c){
int n = grid[i+r][j+c];
if ( n == 0 || n > 9) return false;
valid[n-1]++;
}
}
for(auto& v: valid){
if(v > 1 || v == 0) return false;
}
return true;
}
int isSumValid(vector<vector<int>>& grid, int i, int j){
int row_sum[3]{0}, col_sum[3]{0};
for(int r = 0; r < 3; ++r){
for(int c = 0; c < 3; ++c){
row_sum[r] += grid[i+r][j+c];
col_sum[c] += grid[i+r][j+c];
}
}
for(int i = 0; i < 3; ++c){
if(row_sum[i] !=15 || col_sum[i] != 15) return false;
}
int diagonal_sum = grid[i][j] + grid[i+1][j+1] + grid[i+2][j+2];
int diagonal_sum2 = grid[i][j+2] + grid[i+1][j+1] + grid[i+2][j];
return diagonal_sum == diagonal_sum2;
}
int numMagicSquaresInside(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size(), ans = 0;
if(m < 3 || n < 3) return 0;
for(int i = 0; i < m-2;++i){
for(int j = 0; j < n-2;++j){
if(!isNumsValid(grid, i, j)) continue;
if(!isSumValid(grid, i, j)) continue;
ans++;
}
}
return ans;
}
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.228.99.39 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1723170109.A.022.html
推
08/09 10:23,
1年前
, 1F
08/09 10:23, 1F
推
08/09 10:27,
1年前
, 2F
08/09 10:27, 2F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 679 之 1548 篇)：