【LeetCode36】有效的数独(哈希表)

简介: 从左往右,从上往下遍历给定的二维数组board,然后遍历到当前元素board[i][j]时,需要判断是否满足题目的3个条件,这里可以分别用3个哈希表实现:

一、题目

image.pngimage.pngimage.png




二、思路

从左往右,从上往下遍历给定的二维数组board,然后遍历到当前元素board[i][j]时,需要判断是否满足题目的3个条件,这里可以分别用3个哈希表实现:


在第 i 个行中是否出现过:使用row[9][10],注意第二维度是装的数字,即哈希表的key为数字(1-9范围内),value为是否出现过,出现过则为1(此时就直接返回false了),没出现过即保持为0(事后要置为1)。

在第 j 个列中是否出现过:使用col[9][10]

在第 j/3 + (i/3)*3个box中是否出现过:使用box[9][10]

因为宫格里的数字是1~9范围内,我们可以直接用数组实现哈希表,此时数组大小就设为10了,因为下标从0开始。


三、代码

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        //存储每一行的每一个数是否都出现过
        int row[9][10] = {0};
        int col[9][10] = {0};
        //存储每一个box的每个数是否出现过
        int box[9][10] = {0};
        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                if(board[i][j] == '.') continue;
                int num_temp = board[i][j] - '0';
                //哈希表,判断该数是否在所在的行出现过
                if(row[i][num_temp]) return false;
                if(col[j][num_temp]) return false;
                if(box[j/3 + (i / 3) * 3][num_temp]) return false;
                //现在出现了,对应哈希表的value要置为1
                row[i][num_temp] = 1;
                col[j][num_temp] = 1;
                box[j/3 + (i / 3) * 3][num_temp] = 1;
            }
        }
        return true;
    }
};
相关文章
|
6月前
|
存储
【每日一题Day132】LC23633合并相似的物品 | 哈希表 排序+双指针
【每日一题Day132】LC23633合并相似的物品 | 哈希表 排序+双指针
51 0
|
6月前
|
存储
【每日一题Day158】LC2395和相等的子数组 | 哈希表
【每日一题Day158】LC2395和相等的子数组 | 哈希表
30 0
|
5月前
|
索引
力扣随机一题 6/26 哈希表 数组 思维
力扣随机一题 6/26 哈希表 数组 思维
36 0
|
5月前
力扣随机一题 哈希表 排序 数组
力扣随机一题 哈希表 排序 数组
32 1
|
6月前
|
算法
[leetcode] 哈希表
[leetcode] 哈希表
|
6月前
|
存储
leetcode刷题之哈希表的应用(1)
leetcode刷题之哈希表的应用(1)
30 0
|
6月前
|
API 索引
【每日一题Day346】LC1488避免洪水泛滥 | 贪心+哈希表
【每日一题Day346】LC1488避免洪水泛滥 | 贪心+哈希表
49 0
|
6月前
|
人工智能
LeetCode刷题Day07——哈希表(n数之和、数组交集)
常见的三种哈希结构: 数组 set(集合) map(映射) 数组对于那些知道长度的题目比较适宜,因为map的空间消耗要比数组的大,所以有的时候用数组更贱简单有效。但是数组的大小是有限的,受到系统栈空间(不是数据结构的栈)的限制。如果数组空间够大,但哈希值比较少、特别分散、跨度非常大,使用数组就造成空间的极大浪费,这时候可以考虑采用set。set是一个集合,里面放的元素只能是一个key,而有的题目还需要记录一些额外的信息,如下标或出现次数,这时候可以考虑用map。
【LeetCode36】有效的数独(哈希表)
【LeetCode36】有效的数独(哈希表)
43 0
下一篇
无影云桌面