Leetcode: 【每日一题】- 2019-09-10 - 36. 有效的数独

[azl397985856]

今天的题编程之美和lc都有，这道题有多种解答，请尽量使用多种方法解决。

题目描述

判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

上图是一个部分填充的有效的数独。

数独部分空格内已填入了数字，空白格用 '.' 表示。

示例 1:

输入:
[
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
输出: true
示例 2:

输入:
[
  ["8","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
输出: false

解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。
但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
说明:

一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
给定数独序列只包含数字 1-9 和字符 '.' 。
给定数独永远是 9x9 形式的。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-sudoku
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[xiongcaihu]

思路有点土：

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

``` .js
/**

• 
  
  
  
  • @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;

};
```

[raof01]

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;
    }
};

[azl397985856]

思路有点土：

首先检查行，每行一个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;
};

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

[azl397985856]

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

[maninbule]

领取

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;

    }
};

[azl397985856]

领取

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