【每日一题】- 2019-09-10 - 36. 有效的数独 about leetcode HOT 6 CLOSED

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        for (auto i = 0; i < 9; ++i) {
            auto rowFlag = vector<bool>(10, false);
            auto colFlag = vector<bool>(10, false);
            auto blockFlag = vector<bool>(10, false);
            for (auto j = 0; j < 9; ++j) {
                if (board[i][j] != '.') {
                    auto num = board[i][j] - '0';
                    if (rowFlag[num]) return false;
                    rowFlag[num] = true;
                }
                if (board[j][i] != '.') {
                    auto num = board[j][i] - '0';
                    if (colFlag[num]) return false;
                    colFlag[num] = true;
                }
                auto row = (i/3)*3 + j/3;
                auto col = (i%3)*3 + j%3;
                if (board[row][col] != '.') {
                    auto num = board[row][col] - '0';
                    if (blockFlag[num]) return false;
                    blockFlag[num] = true;
                }
            }
        }
        return true;
    }
};

from leetcode.

思路有点土：

首先检查行，每行一个map记录出现的数字，如果重复，立马结束，返回false
再检查列，思路同行的检查
最后检查九宫格，这里我直接手写坐标，放在数组里，然后挨个遍历

/**
 * 
 * @param {character[][]} board
 * @return {boolean}
 */
var isValidSudoku = function (board) {
    // 检查行
    for (var i = 0; i < board.length; i++) {
        var map = {};
        for (var j = 0; j < board[i].length; j++) {
            if (board[i][j] == '.') continue;
            if (map[board[i][j]]) {
                return false;
            } else {
                map[board[i][j]] = 1;
            }
        }
    }

    // 检查列
    for (var i = 0; i < 9; i++) {
        var map = {};
        for (var j = 0; j < 9; j++) {
            if (board[j][i] == '.') continue;
            if (map[board[j][i]]) {
                return false;
            } else {
                map[board[j][i]] = 1;
            }
        }
    }

    // 检查九宫格
    var startAndEnd = [
        [0, 2, 0, 2], // [0]:行的起始位置，[1]：行的结束位置，[2]：列的起始位置，[3]：列的结束位置
        [0, 2, 3, 5],
        [0, 2, 6, 8],
        [3, 5, 0, 2],
        [3, 5, 3, 5],
        [3, 5, 6, 8],
        [6, 8, 0, 2],
        [6, 8, 3, 5],
        [6, 8, 6, 8]
    ]

    for (var i = 0; i < startAndEnd.length; i++) {
        var item = startAndEnd[i];
        var map = {};
        for (var j = item[0]; j <= item[1]; j++) {
            for (var n = item[2]; n <= item[3]; n++) {
                if (board[j][n] == '.') continue;
                if (map[board[j][n]]) {
                    return false;
                } else {
                    map[board[j][n]] = 1;
                }
            }
        }
    }

    return true;
};

from leetcode.

思路有点土：

首先检查行，每行一个map记录出现的数字，如果重复，立马结束，返回false
再检查列，思路同行的检查
最后检查九宫格，这里我直接手写坐标，放在数组里，然后挨个遍历

/**
 * 
 * @param {character[][]} board
 * @return {boolean}
 */
var isValidSudoku = function (board) {
    // 检查行
    for (var i = 0; i < board.length; i++) {
        var map = {};
        for (var j = 0; j < board[i].length; j++) {
            if (board[i][j] == '.') continue;
            if (map[board[i][j]]) {
                return false;
            } else {
                map[board[i][j]] = 1;
            }
        }
    }

    // 检查列
    for (var i = 0; i < 9; i++) {
        var map = {};
        for (var j = 0; j < 9; j++) {
            if (board[j][i] == '.') continue;
            if (map[board[j][i]]) {
                return false;
            } else {
                map[board[j][i]] = 1;
            }
        }
    }

    // 检查九宫格
    var startAndEnd = [
        [0, 2, 0, 2], // [0]:行的起始位置，[1]：行的结束位置，[2]：列的起始位置，[3]：列的结束位置
        [0, 2, 3, 5],
        [0, 2, 6, 8],
        [3, 5, 0, 2],
        [3, 5, 3, 5],
        [3, 5, 6, 8],
        [6, 8, 0, 2],
        [6, 8, 3, 5],
        [6, 8, 6, 8]
    ]

    for (var i = 0; i < startAndEnd.length; i++) {
        var item = startAndEnd[i];
        var map = {};
        for (var j = item[0]; j <= item[1]; j++) {
            for (var n = item[2]; n <= item[3]; n++) {
                if (board[j][n] == '.') continue;
                if (map[board[j][n]]) {
                    return false;
                } else {
                    map[board[j][n]] = 1;
                }
            }
        }
    }

    return true;
};

简单粗暴，只是后面手写坐标吓到我我了

from leetcode.

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        for (auto i = 0; i < 9; ++i) {
            auto rowFlag = vector<bool>(10, false);
            auto colFlag = vector<bool>(10, false);
            auto blockFlag = vector<bool>(10, false);
            for (auto j = 0; j < 9; ++j) {
                if (board[i][j] != '.') {
                    auto num = board[i][j] - '0';
                    if (rowFlag[num]) return false;
                    rowFlag[num] = true;
                }
                if (board[j][i] != '.') {
                    auto num = board[j][i] - '0';
                    if (colFlag[num]) return false;
                    colFlag[num] = true;
                }
                auto row = (i/3)*3 + j/3;
                auto col = (i%3)*3 + j%3;
                if (board[row][col] != '.') {
                    auto num = board[row][col] - '0';
                    if (blockFlag[num]) return false;
                    blockFlag[num] = true;
                }
            }
        }
        return true;
    }
};

整体代码还是很容易懂的，就是blockFlag部分的row和col有点技巧。

 auto row = (i/3)*3 + j/3;
 auto col = (i%3)*3 + j%3

from leetcode.

领取

class Solution {
public:
    bool visrow[10],viscol[10],vis3x3[10];
    bool isValidSudoku(vector<vector<char>>& board) {
        for(int i  = 0;i<9;i++){ //同时遍历行列
            memset(visrow,0,sizeof visrow);
            memset(viscol,0,sizeof viscol);
            for(int j = 0;j<9;j++){
                if(board[i][j]!='.'){
                    if(visrow[board[i][j]-'0']) return false;
                    else visrow[board[i][j]-'0'] = 1;
                }
                if(board[j][i]!='.'){
                    if(viscol[board[j][i]-'0']) return false;
                    else viscol[board[j][i]-'0'] = 1;
                }
            }
        }
        for(int i = 0;i<9;i+=3){//遍历每个3x3的左上角
            for(int j = 0;j<9;j+=3){
                memset(vis3x3,0,sizeof vis3x3);
                for(int ii = i;ii<i+3;ii++){
                    for(int jj = j;jj<j+3;jj++){
                        if(board[ii][jj]!='.'){
                            if(vis3x3[board[ii][jj]-'0']) return false;
                            else vis3x3[board[ii][jj]-'0'] = 1;
                        }
                    }
                }
            }
        }
        return true;

    }
};

from leetcode.

领取

class Solution {
public:
    bool visrow[10],viscol[10],vis3x3[10];
    bool isValidSudoku(vector<vector<char>>& board) {
        for(int i  = 0;i<9;i++){ //同时遍历行列
            memset(visrow,0,sizeof visrow);
            memset(viscol,0,sizeof viscol);
            for(int j = 0;j<9;j++){
                if(board[i][j]!='.'){
                    if(visrow[board[i][j]-'0']) return false;
                    else visrow[board[i][j]-'0'] = 1;
                }
                if(board[j][i]!='.'){
                    if(viscol[board[j][i]-'0']) return false;
                    else viscol[board[j][i]-'0'] = 1;
                }
            }
        }
        for(int i = 0;i<9;i+=3){//遍历每个3x3的左上角
            for(int j = 0;j<9;j+=3){
                memset(vis3x3,0,sizeof vis3x3);
                for(int ii = i;ii<i+3;ii++){
                    for(int jj = j;jj<j+3;jj++){
                        if(board[ii][jj]!='.'){
                            if(vis3x3[board[ii][jj]-'0']) return false;
                            else vis3x3[board[ii][jj]-'0'] = 1;
                        }
                    }
                }
            }
        }
        return true;

    }
};

done

from leetcode.