Re: [閒聊] 每日leetcode
這題滿無聊的
用暴力法就可以了
寫起來超醜
840. Magic Squares In Grid
magic square是指3*3的grid包含1~9
每個數字只會出現一次
且每行、每列、對角線的總和都會一樣
給你一個row*col grid請求出有幾個magic square
思路:
因為1~9的等差數列總合為45
然後每行、每列的總和要相等 : 45/3=15
15就是那個總和
然後要達到magic square，中心一定要是5
確認條件後就for迴圈下去檢查
就可以得到答案了
golang code：
func numMagicSquaresInside(grid [][]int) int {
n, m, ans := len(grid), len(grid[0]), 0
if n < 3 || m < 3 {
return 0
}
for i := 0; i < n-2; i++ {
for j := 0; j < m-2; j++ {
ans += chk(grid, i, j)
}
}
return ans
}
func chk(arr [][]int, i, j int) int {
rec := make([]bool, 9)
if arr[i+1][j+1] != 5 {
return 0
}
diagonal_1, diagonal_2 := arr[i][j]+arr[i+1][j+1]+arr[i+2][j+2], arr[i][j+2]+
arr[i+1][j+1]+arr[i+2][j]
if diagonal_1 != 15 || diagonal_2 != 15 {
return 0
}
c_sum := [3]int{}
for x := i; x < i+3; x++ {
r_sum := 0
c_sum[0] += arr[x][j]
c_sum[1] += arr[x][j+1]
c_sum[2] += arr[x][j+2]
for y := j; y < j+3; y++ {
if arr[x][y] > 9 || arr[x][y] == 0 || rec[arr[x][y]-1] {
return 0
}
rec[arr[x][y]-1] = true
r_sum += arr[x][y]
}
if r_sum != 15 {
return 0
}
}
for i := 0; i < 3; i++ {
if c_sum[i] != 15 {
return 0
}
}
return 1
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.137.51.54 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1723223345.A.DAC.html
推
08/10 01:09,
1年前
, 1F
08/10 01:09, 1F
推
08/10 01:10,
1年前
, 2F
08/10 01:10, 2F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 684 之 1548 篇)：