Valid Sudoku -- LeetCode

這道題是Sudoku Solver的一個子問題，在解數獨的時候我們需要驗證當前數盤是否合法。其實思路比較簡單，也就是用brute force。對於每一行，每一列，每個九宮格進行驗證，總共需要27次驗證，每次看九個元素。所以時間復雜度就是O(3*n^2), n=9。代碼如下：

public boolean isValidSudoku(char[][] board) {
    if(board==null || board.length!=9 || board[0].length!=9)
        return false;
    for(int i=0;i<9;i++)
    {
        boolean[] map = new boolean[9];
        for(int j=0;j<9;j++)
        {
            if(board[i][j] != '.')
            {
                if(map[(int)(board[i][j]-'1')])
                {
                    return false;
                }
                map[(int)(board[i][j]-'1')] = true;
            }
        }
    }
    for(int j=0;j<9;j++)
    {
        boolean[] map = new boolean[9];
        for(int i=0;i<9;i++)
        {
            if(board[i][j] != '.')
            {
                if(map[(int)(board[i][j]-'1')])
                {
                    return false;
                }
                map[(int)(board[i][j]-'1')] = true;
            }
        }
    }        
    for(int block=0;block<9;block++)
    {
        boolean[] map = new boolean[9];
        for(int i=block/3*3;i這道題其實沒有什麼好的算法，基本上就是遍歷去檢查，實現上就是數組的操作，屬於Sudoku
 Solver的subroutine，但是在Sudoku
 Solver中實現上又可以進行優化，沒必要每次檢查整個board，只需要看當前加進去的數就可以，有興趣的朋友可以看看哈。