Re: [閒聊] 每日LeetCode
※ 引述《Rushia (みけねこ的鼻屎)》之銘言：
: 36. Valid Sudoku
: 給你一個二維字元陣列表示一個數獨，包含1~9和表示空白的.字元，一個合法數獨
: 滿足以下條件：
: 1.每行和每列最多出現一種數字一次
: 2.一個3x3九宮格內只會出現一種數字一次
: 3.數獨可能無解（無法填滿數字），但是只有滿足1或2才是Invalid
: 判斷給定的棋盤是否是一個合法數獨
: Example：
: https://upload.wikimedia.org/wikipedia/commons/thumb/f/ff/Sudoku-by-L2G-20050714.svg/250px-Sudoku-by-L2G-20050714.svg.png
: Input: board =
: [["5","3",".",".","7",".",".",".","."]
: ,["6",".",".","1","9","5",".",".","."]
: ,[".","9","8",".",".",".",".","6","."]
: ,["8",".",".",".","6",".",".",".","3"]
: ,["4",".",".","8",".","3",".",".","1"]
: ,["7",".",".",".","2",".",".",".","6"]
: ,[".","6",".",".",".",".","2","8","."]
: ,[".",".",".","4","1","9",".",".","5"]
: ,[".",".",".",".","8",".",".","7","9"]]
: Output: true
思路:
1. 每個直排/橫排/九宮格都開一個 set 去記
檢查數字有沒有在自己屬於的 set 裡出現過
犧牲了一點空間
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
vset = [set() for i in range(9)]
hset = [set() for i in range(9)]
bset = [[set() for i in range(3)] for j in range(3)]
for i in range(9):
for j in range(9):
if board[i][j] == '.':
continue
elif board[i][j] in vset[i] or board[i][j] in hset[j] or
board[i][j] in bset[i//3][j//3]:
return False
else:
vset[i].add(board[i][j])
hset[j].add(board[i][j])
bset[i//3][j//3].add(board[i][j])
return True
--
蛤?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.251.216.212 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1669173580.A.290.html
推
11/23 11:23,
3年前
, 1F
11/23 11:23, 1F
→
11/23 18:17,
3年前
, 2F
11/23 18:17, 2F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 115 之 719 篇)：