LeetCode(38)-Valid Sudoku

时间:2021-11-09 02:23:09

题目:

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 '.'.

![这里写图片描述](http://img.blog.csdn.net/20160409183641502)
A partially filled sudoku which is valid.

A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

思路:

  • 首先这是一道数独题目,关于数独的性质,可以参考下面的链接

    数独规则

  • 考虑根据数独的各个条件来逐个解决,需要判断每行,每一列,以及每个小方格是否是1~9,出现一次,思路是建立一个list添加,判断是否出现重复,出现返回false;同样如果board == null,或者行数和列数不等于9,也返回false

  • -

代码:

public class Solution {
    public boolean isValidSudoku(char[][] board) {
        ArrayList<ArrayList<Character>> rows = new ArrayList<ArrayList<Character>>();
        ArrayList<ArrayList<Character>> cols = new ArrayList<ArrayList<Character>>();
        ArrayList<ArrayList<Character>> boxs = new ArrayList<ArrayList<Character>>();
        if(board == null || board.length != 9|| board[0].length != 9){
            return false;
        }
        for(int i = 0;i < 9;i++){
            rows.add(new ArrayList<Character>());
            cols.add(new ArrayList<Character>());
            boxs.add(new ArrayList<Character>());
        }
        for(int a = 0;a < board.length;a++){
            for(int b = 0;b < board[0].length;b++){
                if(board[a][b] == '.'){
                    continue;
                }
                ArrayList<Character> row = rows.get(a);
                if(row.contains(board[a][b])){
                    return false;
                }else{
                    row.add(board[a][b]);
                }
                ArrayList<Character> col = cols.get(b);
                if(col.contains(board[a][b])){
                    return false;
                }else{
                    col.add(board[a][b]);
                }
                ArrayList<Character> box = boxs.get(getNum(a,b));
                if(box.contains(board[a][b])){
                    return false;
                }else{
                    box.add(board[a][b]);
                }
            }
        }return true;
    }
    public int getNum(int i,int j){
        return (i/3)*3+j/3;
    }
}