Re: [閒聊] 每日leetcode
840. Magic Squares In Grid
## 思路
中間放5 然後照題目檢查col/row/diag sum
其他作法
要符合1~9又sum=15的可能
填下去只會有這種組合 (對角2,4,6,8)
2 9 4
7 5 3
8 1 6
-> 2,7,8,1,6,3,4,9 (逆時針)
-> 2,9,4,3,6,1,8,7 (順時針)
感覺可以把外圍8個數字照順時鐘列出來
再對這兩種sequence*2 做match
不過我懶的寫
## Complexity
Time: O(RC)
Space: O(1)
## Code
```python
"""
2 9 4 a1 a2 a3
7 5 3 a4 a5 a6
6 1 8 a7 a8 a9
"""
class Solution:
def numMagicSquaresInside(self, grid: List[List[int]]) -> int:
len_r, len_c = len(grid), len(grid[0])
def is_magic(r, c):
if grid[r+1][c+1] != 5:
return False
arr = [grid[r+dr][c+dc] for dr in range(3) for dc in range(3)]
# check distinct 1~9
if set(arr) != set(range(1, 10)):
return False
# check row
for i in range(0, 9, 3):
if arr[i] + arr[i+1] + arr[i+2] != 15:
return False
# check col
for i in range(3):
if arr[i] + arr[i+3] + arr[i+6] != 15:
return False
# check diag
for i in {0, 2}:
if arr[i] + arr[~i] != 10:
return False
return True
res = 0
for r in range(len_r-2):
for c in range(len_c-2):
if is_magic(r, c):
res += 1
return res
```
--
http://i.imgur.com/OLvBn3b.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 185.213.82.247 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1723166068.A.899.html
→
08/09 10:27,
1年前
, 1F
08/09 10:27, 1F
討論串 (同標題文章)
完整討論串 (本文為第 675 之 1548 篇)：