【数据结构入门_链表】 Leetcode 36.有效的数独

原题链接：Leetcode 36. Valid Sudoku

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.
Note:

A Sudoku board (partially filled) could be valid but is not necessarily solvable.
Only the filled cells need to be validated according to the mentioned rules.

Example 1:

Input: board = 
[["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"]]
Output: true

Example 2:

Input: board = 
[["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"]]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

Constraints:

• board.length == 9
• board[i].length == 9
• board[i][j] is a digit 1-9 or ‘.’.

方法一：一次遍历 + 哈希表

思路：

本题只要求判断是否满足数独的条件即可，并非求解
满足数独的条件是，同一行、同一列、同一个3*3的小九宫格内一个数只能出现一次
那么用3个哈希表来记录出现次数，遍历一遍哈希表，当某个元素在其中的一个哈希表中出现了2次就返回false
因为判断的是数字1-9，因此可以数组来实现哈希表

c++代码:

class Solution {
public:bool isValidSudoku(vector<vector<char>>& board) {// 三个哈希表来记录 每行、列、小九宫格中数出现的次数int row[9][9] = {0};int col[9][9] = {0};int block[3][3][9] = {0};// 遍历每个元素for(int i = 0; i < 9; i++ ){for(int j = 0; j < 9; j++ ){char c = board[i][j];if(c != '.'){// 元素的值int val = c - '0' - 1;row[i][val] += 1;col[j][val] += 1;block[i / 3][j / 3][val] += 1;if(row[i][val] > 1 || col[j][val] > 1 || block[i/3][j/3][val] > 1)return false;}}}return true;}
};

复杂度分析：

• 时间复杂度：O(1)，题目中数独固定是9*9=81个元素
• 空间复杂度：O(1)

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！