力扣题解 36th 有效的数独

36th 有效的数独

• 哈希表思想与二维数组区块(section)的划分

  首先，采用哈希表思想保证数字1-9只出现一次。

  其次，对于条件1和条件2我们很容易写出对应的hash table并填充好数据，但是对于条件3我们需要将二位数组进行区块拆封。

  区块拆封方法：

  • 分析过程：已知原数组容量为9x9，则以一个3x3为区块拆分后，二维数组容量为为3x3。当i=0或1或2，j=0或1或2时，i/3始终为0，j/3始终为0。以此类推可用i/3，j/3来定位新的3x3数组。

  class Solution {
      public boolean isValidSudoku(char[][] board) {
          int[][] table_raw = new int[9][10];
          int[][] table_column = new int[9][10];
          int[][][] table_section = new int[3][3][10];
  
          for (int i = 0; i < 9; i++) {
              for (int j = 0; j < 9; j++) {
                  // raw
                  if (board[i][j] != '.')
                      table_raw[i][board[i][j] - '0']++;
                  // column
                  if (board[j][i] != '.')
                      table_column[i][board[j][i] - '0']++;
                  // section
                  if (board[i][j] != '.')
                      table_section[i / 3][j / 3][board[i][j] - '0']++;
              }
          }
  
          for (int i = 0; i < 9; i++) {
              for (int j = 0; j < 10; j++) {
                  if (table_raw[i][j] > 1 || table_column[i][j] > 1)
                      return false;
              }
          }
          for (int i = 0; i < 3; i++) {
              for (int j = 0; j < 3; j++) {
                  for (int k = 0; k < 10; k++) {
                      if (table_section[i][j][k] > 1)
                          return false;
                  }
              }
          }
          return true;
      }
  }