聖地亞歌

Leetcode P0036"Valid Sudoku" 题解

2020/08/22 Leetcode

博文中会简要介绍Leetcode P0036题目分析及解题思路。

“Valid Sudoku”属于“看图看题说话”的风格。按照题目中的要求写出判断公式即可。这里可以不用HashTable来记录数字出现个数，这样可以减少时间开销。

Determine if a 9x9 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 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.

以下是Java的题解代码实现。

class Solution {
    public boolean isValidSudoku(char[][] board) {
        int[][][] digitCounterForSubbox = new int[3][3][10];
        int[][] digitCounterForRow = new int[9][10];
        int[][] digitCounterForCol = new int[9][10];
        
        for (int row=0; row<9; ++row) {
            for (int col=0; col<9; ++col) {
                if (board[row][col] == '.')
                    continue;
                
                int digit = board[row][col]-'0';
                ++digitCounterForRow[row][digit];
                ++digitCounterForCol[col][digit];
                
                ++digitCounterForSubbox[row/3][col/3][digit];
                
                if (digitCounterForRow[row][digit] > 1 
                    || digitCounterForCol[col][digit] > 1 
                    || digitCounterForSubbox[row/3][col/3][digit] > 1) {
                    return false;
                }
            }
        }
        
        return true;
    }
}
Java

Search