iT邦幫忙

2021 iThome 鐵人賽

DAY 10
0
自我挑戰組

30天 Leetcode解題之路系列 第 10

Day 10 - Valid Sudoku

大家好,我是毛毛。ヾ(´∀ ˋ)ノ
廢話不多說開始今天的解題Day~

tags: 2021_iThome鐵人賽 Leetcode

36. Valid Sudoku

Question

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

  1. Each row must contain the digits 1-9 without repetition.
  2. Each column must contain the digits 1-9 without repetition.
  3. Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

Note:

  • A Sudoku board (partially filled) could be valid but is not necessarily solvable.
  • Only the filled cells need to be validated according to the mentioned rules.

Example

Example1

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

Example2

Input: board = 
[["8","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: false
Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

Constraints

  • board.length == 9
  • board[i].length == 9
  • board[i][j] is a digit 1-9 or '.'.

解題

題目

首先先簡單的翻譯一下題目
給一個數獨題目要你解,給一個數獨題目要判斷這個數獨題目是不是合乎數獨的規則,也就是不管是行、列和9塊3 x 3的區塊,出現的數字1-9皆不能重複。

Think

作法大致上是這樣

  • 本來一開始是打算用for loop做,但是忽然想到有enumerate可以使用,enumerate有點像for rowVal in board:的方式,只是每個值會在額外配上一個sequence,這個sequence的起始可以透過start參數來決定。
  • 因為有行、列和區塊要判斷,所以就分三個部份分別處理。
  • 下面避免行列混淆,用RowColumn來說明。
  • Row part & Column part
    • rowcol這兩個list存著已經出現過的值,假如新讀到的值已經有存在裡頭了,就代表重複了,回傳False;沒有的話,就存入。
    • 存入的值為(seq, value)搭配
  • subBox part
    • subBox這個list存著已經出現過的值,假如新讀到的值已經有存在裡頭了,就代表重複了,回傳False;沒有的話,就存入。
    • 存入的值是取seq/3的商,這邊我用轉int把小數部分捨去了。
    • 這樣可以得到9個區塊分別的代碼:
      • 0,00,10,2
      • 1,01,11,2
      • 2,02,12,2
    • 在配上每個點的value就可以透過subBox的list判斷有沒有重複數字了。
  • C的程式出了點問題QQ,再補上。

Code

Python

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        row = []
        col = []
        subBox = []
        
        for seq1, rowVal in enumerate(board, start=0):
            for seq2, colVal in enumerate(rowVal, start=0):

                if colVal is not ".":
                    # Row part
                    if (seq1, colVal) not in row:
                        row.append((seq1, colVal))
                    else:
                        return False

                    # Column part
                    if (seq2, colVal) not in col:
                        col.append((seq2, colVal))
                    else:
                        return False
                
                    # subBox part
                    if (int(seq1/3), int(seq2/3), colVal) not in subBox:
                        subBox.append((int(seq1/3), int(seq2/3), colVal))
                    else:
                        return False
        return True

C


Result

  • Python

  • C

大家明天見/images/emoticon/emoticon29.gif


上一篇
Day 9 - Container With Most Water
下一篇
Day 11 - Roman to Integer
系列文
30天 Leetcode解題之路30

尚未有邦友留言

立即登入留言