We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
出处:LeetCode 算法第36题 判断一个 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 算法第36题
判断一个 9x9 的数独是否有效。只需要根据以下规则,验证已经填入的数字是否有效即可。
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 存在, 因此这个数独是无效的。
说明:
9x9
本题是一个二维数组,如果用暴力破解会有很高的时间复杂度,所以我们可以定义几个map,通过空间换时间的方式来降低时间复杂度
var isValidSudoku = function (board) { var flag = true; for (var i = 0; i < 9; i++) { var rowMap = {}; var colMap = {}; var cubeMap = {}; for (var j = 0; j < 9; j++) { if (board[i][j] != '.') { if (rowMap[board[i][j]] == true) { flag = false; } else { rowMap[board[i][j]] = true; } } if (board[j][i] != '.') { if (colMap[board[j][i]] == true) { flag = false; } else { colMap[board[j][i]] = true; } } var RowIndex = 3 * Math.floor(i / 3) + Math.floor(j / 3); // 列号+偏移量 var ColIndex = 3 * Math.floor(i % 3) + Math.floor(j % 3); if (board[RowIndex][ColIndex] != '.') { if (cubeMap[board[RowIndex][ColIndex]] == true) { flag = false; } else { cubeMap[board[RowIndex][ColIndex]] = true; } } } } return flag; };
The text was updated successfully, but these errors were encountered:
No branches or pull requests
题目
思路
本题是一个二维数组,如果用暴力破解会有很高的时间复杂度,所以我们可以定义几个map,通过空间换时间的方式来降低时间复杂度
解答
The text was updated successfully, but these errors were encountered: