`

Leetcode - Valid Sudoku

 
阅读更多
Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.
The Sudoku board could be partially filled, where empty cells are filled with the character '.'.
Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.
[分析] 九宫格规则:每一行,每一列,每个3*3的区块的9个数字恰好为1-9,不能有重复。
注意3*3的区块为行列三等分形成的,共9个,而不是任意的3*3区块。 此题对我来说难点在于3*3区块下标的表示上,方法2参照https://leetcode.com/discuss/45494/java-solution-easy-to-understand,代码非常简洁。

public class Solution {
    // Method 2
    public boolean isValidSudoku(char[][] board) {
        boolean[][] rows = new boolean[9][9];
        boolean[][] cols = new boolean[9][9];
        boolean[][] block = new boolean[9][9];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.')
                    continue;
                int digit = board[i][j] - '1';
                int blockId = i / 3 * 3 + j / 3;
                
                if (rows[i][digit]) return false;
                else rows[i][digit] = true;
                
                if (cols[j][digit]) return false;
                else cols[j][digit] = true;
                
                if (block[blockId][digit]) return false;
                else block[blockId][digit] = true;
            }
        }
        return true;
    }
    
    // Method 1
    public boolean isValidSudoku1(char[][] board) {
        boolean[] used = new boolean[board.length + 1];
        int n = board.length;
        //check each row
        for(int i = 0; i < n; i++){
            used = new boolean[n + 1];
            for(int j = 0; j < n; j++)
                if(board[i][j] == '.')
                    continue;
                else if(!used[board[i][j] - '0'])
                    used[board[i][j] - '0'] = true;
                else
                    return false;
        }
        
        //check each column
        for(int j = 0; j < n; j++){
            used = new boolean[n + 1];
            for(int i = 0; i < n; i++)
                if(board[i][j] == '.')
                    continue;
                else if(!used[board[i][j] - '0'])
                    used[board[i][j] - '0'] = true;
                else
                    return false;
        }
        
        //check for each block
        for(int r = 0; r < 3; r++){
            for(int c = 0; c < 3; c++){
                used = new boolean[n + 1];
                int x = 3 * r;
                int y = 3 * c;
                for(int i = 0; i < 3; i++){
                    for(int j = 0; j < 3; j++){
                        if(board[x + i][y + j] == '.')
                            continue;
                        else if(!used[board[x + i][y + j] - '0'])
                            used[board[x + i][y + j] - '0'] = true;
                        else
                            return false;
                    }
                }
            }
        }
        
        return true;
    }
}
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics