text: '''
  有效的数独
  判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
  
  数字 1-9 在每一行只能出现一次。
  数字 1-9 在每一列只能出现一次。
  数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
  
  数独部分空格内已填入了数字，空白格用 '.' 表示。
  '''
  
  from typing import List
  '''
  思路：遍历每一行，每一列，每一9宫格。
  因为只有9个元素，可以用1个整数的位运算，节省空间，初始化快
  时间复杂度：O(n^2)
  空间复杂度：O(n)
  '''
  
  
  class Solution:
      def isValidSudoku(self, board: List[List[str]]) -> bool:
          col = [0] * 9  # 所有列
          nine = [0] * 9  # 九宫格
          for i in range(9):
              row = 0  # 一行
              for j in range(9):
                  s = board[i][j]
                  if s.isdigit():
                      n = int(s)
                      bit = 1 << n
                      if row & bit:
                          return False
                      else:
                          row |= bit
                      if col[j] & bit:
                          return False
                      else:
                          col[j] |= bit
                      nineIdx = i // 3 * 3 + j // 3
                      if nine[nineIdx] & bit:
                          return False
                      else:
                          nine[nineIdx] |= bit
          return True
  
  
  s = Solution()
  print(
      s.isValidSudoku([["7", ".", ".", ".", "4", ".", ".", ".", "."], [".", ".", ".", "8", "6", "5", ".", ".",
                                                                       "."], [".", "1", ".", "2", ".", ".", ".", ".", "."],
                       [".", ".", ".", ".", ".", "9", ".", ".", "."], [".", ".", ".", ".", "5", ".", "5", ".",
                                                                       "."], [".", ".", ".", ".", ".", ".", ".", ".", "."],
                       [".", ".", ".", ".", ".", ".", "2", ".", "."], [".", ".", ".", ".", ".", ".", ".", ".", "."],
                       [".", ".", ".", ".", ".", ".", ".", ".", "."]]))
  print(
      s.isValidSudoku([["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"]]))
  print(
      s.isValidSudoku([["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"]]))
  