[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 '.'.
这个数独面板部分填充,空白部分“.”代替。

维基图片

A partially filled sudoku which is valid.
判断一个未填充完成数独是否合法
Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

注意:
只需判断数独是否重复,无需判断是否可行。

解析,暴力解法

比较标准的 O(n^2) X 3.

class Solution {
public:
    bool isValidSudoku(vector< vector<char> >& board) {
        int a = 0;
        set <int> row;
        for(int i=0;i<9;i++){ //every row
            for(int j=0;j<9;j++){
                if(board[i][j]=='.') continue;
                if(row.count(board[i][j])){
                    return false;
                } else {
                    row.insert(board[i][j]);
                }
            }
            row.clear();
        }
        for(int i=0;i<9;i++){ //every line
            for(int j=0;j<9;j++){
                if(board[j][i]=='.') continue;
                if(row.count(board[j][i])){
                    return false;
                } else {
                    row.insert(board[j][i]);
                }
            }
            row.clear();
        }
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                if(board[(((i==0?1:i)/3)*3)+j/3][((i%3)*3)+j%3]=='.') continue;
                if(row.count(board[(((i==0?1:i)/3)*3)+j/3][((i%3)*3)+j%3])){
                    return false;
                } else {
                    row.insert(board[(((i==0?1:i)/3)*3)+j/3][((i%3)*3)+j%3]);
                }
            }
            row.clear();
        }
        return true;
    }
};

稍微好一点的方法

一遍哈希,碰撞返回 false

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {

        vector<int> check = {1,2,3,4,5,6,7,8,9};
        for (int i = 0; i <board.size(); i++) {
            vector<int> checkrow = check;
            for (int j = 0; j < board[0].size() ; ++j) {
                if (board[i][j] != '.') {
                    if (checkrow[board[i][j] - '1'] == board[i][j] - '0') {
                        checkrow[board[i][j] - '1'] = 0;
                    } else {
                        return false;
                    }
                }
            }
        }

        for (int j = 0; j < board[0].size() ; ++j) {
            vector<int> checkcol = check;
                for (int i = 0; i <board.size(); i++) {
                if (board[i][j] != '.') {
                    if (checkcol[board[i][j] - '1'] == board[i][j] - '0') {
                        checkcol[board[i][j] - '1'] = 0;
                    } else {
                        return false;
                    }
                }
            }
        }

        for (int r = 0; r <board.size(); r = r + 3) {

            for (int l = 0; l < board[0].size() ; l = l + 3) {
                vector<int> checkblock = check;
                for (int i = r ; i < r + 3 ; ++i) {
                    for (int j = l; j < l + 3; ++j) {
                        if (board[i][j] != '.') {
                            if (checkblock[board[i][j] - '1'] == board[i][j] - '0') {
                                checkblock[board[i][j] - '1'] = 0;
                            } else {
                                return false;
                            }
                        }
                    }
                }

            }
        }

        return true;
    }
};

转载请注明 原文连接

发表评论

电子邮件地址不会被公开。 必填项已用*标注