【每日一题】- 2019-09-10 - 36. 有效的数独 #169
Comments
/**
*
* @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;
};
|
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 |
|
领取 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 |
baicaihenxiao
pushed a commit
to baicaihenxiao/leetcode-frontend
that referenced
this issue
Apr 14, 2020
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
今天的题编程之美和lc都有，这道题有多种解答，请尽量使用多种方法解决。
题目描述
判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
上图是一个部分填充的有效的数独。
数独部分空格内已填入了数字，空白格用 '.' 表示。
解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。
但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
说明:
一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
给定数独序列只包含数字 1-9 和字符 '.' 。
给定数独永远是 9x9 形式的。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-sudoku
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
The text was updated successfully, but these errors were encountered: