LeetCode 36 Valid Sudoku（有效数独）

翻译

数独板被部分填充，空格部分用'.'来填充。

一个部分填充的数组是否有效只需要看其填充的部分即可。

原文

分析

这道题写了一会，错了……因为输入太懒搞了，就直接看了别人写的……

class Solution {
public:
    int a[9];
    bool isValidSudoku(vector<vector<char>>& board) {
        memset(a,0,sizeof(a));
        for (int i=0,j=0,row=0,col=0;i<9;++j,j==9?++i,j=0,row=col=0:0)
        {
            if (board[i][j]!='.')
            {
                if ((1<<board[i][j]-48) & row) return false;
                else row|=1<<board[i][j]-48;
                if ((1<<board[i][j]-48) & a[i/3*3+j/3]) return false;
                else a[i/3*3+j/3]|=1<<board[i][j]-48;
            }
            if (board[j][i]!='.')
                if ((1<<board[j][i]-48) & col) return false;
                else col|=1<<board[j][i]-48;
        }
        return true;
    }
};

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        int i, j, c;
        int row[9][9], col[9][9], block[3][3][9];
        memset(row, 0, sizeof(row));
        memset(col, 0, sizeof(col));
        memset(block, 0, sizeof(block));
        for (i = 0; i < 9; i++) {
            for (j = 0; j < 9; j++) {
                if(board[i][j] != '.'){
                    c = board[i][j] - '1';
                    if (row[i][c] || col[j][c] || block[i / 3][j / 3][c])
                        return false;
                    else {
                        row[i][c] ++;
                        col[j][c] ++;
                        block[i / 3][j / 3][c]++;
                    }
                }
            }
        }
        return true;
    }
};

updated at 2016/09/05

用Java写了一遍，上半部分是横向和纵向遍历，每行使用一次hashmap，用完就clear掉。下半部分是分成9个格子，每个格子里用一个hashmap，也是用完就clear掉。

    public boolean isValidSudoku(char[][] board) {
        if (board == null)
            throw new NullPointerException();
        HashMap<Character, Integer> row = new HashMap<>(9), col = new HashMap<>(9);
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char ch1 = board[i][j], ch2 = board[j][i];
                if (ch1 != '.') {
                    if (row.containsKey(ch1)) return false;
                     else row.put(ch1, 1);
                }
                if (ch2 != '.') {
                    if (col.containsKey(ch2)) return false;
                    else col.put(ch2, 1);
                }
            }
            row.clear();
            col.clear();
        }
        HashMap<Character, Integer> sudoku = new HashMap<>(9);
        for (int r = 0; r <= 6; r+=3) {
            for (int c = 0; c <= 6; c+=3) {
                for (int i = 0; i < 3; i++) {
                    for (int j = 0; j < 3; j++) {
                        char ch = board[i+r][j+c];
                        if (ch != '.') {
                            if (sudoku.containsKey(ch)) return false;
                            else sudoku.put(ch, 1);
                        }
                    }
                }
                sudoku.clear();
            }
        }
        return true;
    }

代码