LeetCode-36. 有效的数独

超、凢脫俗 2024-03-27 04:13 75阅读 0赞

#### 目录 ####

*   *  题目分析
     *  方法一：哈希表
     *  方法二：数组
     *  方法三：位运算

题目来源  
[36. 有效的数独][36.]

### 题目分析 ###

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

> 思考一个问题知道行和列，怎么推出他在几号框  
> ![在这里插入图片描述][4b7dd69883e840b3a892395ee24d2c2c.png]

给定i和j，如何判定board\[i\]\[j\]在第几个box呢？  
显然属于第几个box由i和j的组合唯一确定  
例如board\[2\]\[2\]一定是第0个box  
board\[4\]\[7\]一定是第5个box  
可以画出来看一下，但是规律在哪里呢？ 我们可以考虑一种简单的情况： 一个3x9的矩阵，被分成3个3x3的box，如图：  
![在这里插入图片描述][a7b226ed5a9841748964047d4fd84e17.png]

*  显然每个数属于哪个box就只取决于纵坐标，纵坐标为0/1/2的都属于box\[0\],纵坐标为3/4/5的都属于box\[1\],纵坐标为6/7/8的都属于box\[2\].也就是j/3.
 *  而对于9x9的矩阵，我们光根据j/3得到0/1/2还是不够的，可能加上一个3的倍数，例如加0x3,表示本行的box，加1x3，表示在下一行的box，加2x3，表示在下两行的box， 这里的0/1/2怎么来的？和j/3差不多同理，也就是i/3。

### 方法一：哈希表 ###

当数字只能出现一次时，自然而然会想到哈希。因为哈希集的特点就是不能存重复的值，然后本题就用了哈希表来存不同的行，列和框。当遍历到一个值时，就去查对应的行，列和框的哈希集，如果存在那就是重复了；不存在就将该值放进去。

*  首先建立哈希表用来存不同的行，列和框。
 *  遍历哈希表，将9个行，列，框先放进去。
 *  之后遍历数独，跳过.，然后判断哈希集是否有该值，不存在就将该值加入；存在就返回false。
 *  如果遍历完整个数独都没有重复的，就返回true。

class Solution {
        
        public boolean isValidSudoku(char[][] board) {
        
            HashMap<Integer, Set<Integer>> col = new HashMap<>();
            HashMap<Integer, Set<Integer>> row = new HashMap<>();
            HashMap<Integer, Set<Integer>> box = new HashMap<>();
            for(int i=0;i<9;i++){
        
                col.put(i,new HashSet<>());
                row.put(i,new HashSet<>());
                box.put(i,new HashSet<>());
            }
            for (int i = 0; i < 9; i++) {
        
                for (int j = 0; j < 9; j++) {
        
                    char c = board[i][j];
                    if (c == '.'){
        
                        continue;
                    }
                    int number = c - '0';
                    int boxn = (i/3 *3) + j/3;
                    if (row.get(i).contains(number) || col.get(j).contains(number)|| box.get(boxn).contains(number)){
        
                        return false;
                    }else {
        
                        col.get(j).add(number);
                        row.get(i).add(number);
                        box.get(boxn).add(number);
                    }
                }
            }
            return true;
        }
    }

![在这里插入图片描述][9bb8d0267ec64146b49660d340f8e8ca.png]

### 方法二：数组 ###

row\[\]\[\]中第一维表示的是哪一行，第二维表示的是该行中有哪个值，列和框以此类推。  
如果第i行第n个值不为0，那么说明该行出现过该值，则可以返回false。

*  首先新建三个二维数组用来存储
 *  然后遍历数组，通过数组判断是否出现重复，没出现过就将该值+1；出现就返回false
 *  最后如果没有重复，就返回true

class Solution {
        
        public boolean isValidSudoku(char[][] board) {
        
            int[][] row = new int[9][9];
            int[][] col = new int[9][9];
            int[][] box = new int[9][9];
            for (int i = 0; i < 9; i++) {
        
                for (int j = 0; j < 9; j++) {
        
                    char c = board[i][j];
                    if (c == '.'){
        
                        continue;
                    }
                    //如果不-1数座会越界，比如开始数字是9，row[i][9]越界，也可以不-1，但是初始化开始要为int[][] row = new int[9][10];
                    int number = c - '0' - 1;
                    int boxn = i/3*3 + j/3;
                    if (row[i][number]>0 || col[j][number]>0 || box[boxn][number]>0){
        
                        return false;
                    }else {
        
                        row[i][number]++;
                        col[j][number]++;
                        box[boxn][number]++; 
                    }
                }
            }
            return true;
        }
    }

![在这里插入图片描述][760e6ab6c12b4370960f1709f14a98b8.png]

### 方法三：位运算 ###

假设出现了数字5，那么就将1<<5,也就是1向左移5位，就变成了二进制的（0000 0010 0000）。  
如果再出现了数字3，那也将1<<3，1向左移3位，变成二进制的(0000 0000 1000)。  
通过或操作，也就是|将两个数放在一起，变成了(0000 0010 1000)。以此类推。  
通过且操作，能够判断&数组中的数字中是否存在board\[i\]\[j\]，比如board\[i\]\[j\] = 5，那两者(0000 0010 1000)&（0000 0010 0000）= （0000 0010 0000）。那就返回false。

*  首先新建三个一维数组
 *  遍历数独，跳过.，之后将值变成位元素之后的值。
 *  通过且操作判断是否存在该值，存在就返回false，不存在就通过或操作将该值加入。
 *  遍历完数独，就返回true

class Solution {
        
        public boolean isValidSudoku(char[][] board) {
        
            int[] row = new int[9];
            int[] col = new int[9];
            int[] box = new int[9];
            for (int i = 0; i < 9; i++) {
        
                for (int j = 0; j < 9; j++) {
        
                    char c = board[i][j];
                    if (c == '.') {
        
                        continue;
                    }
                    int number = 1<<(c - '0');
                    int boxn = (i / 3 * 3) + j / 3;
                    if ((row[i] & number) != 0 || (col[j] & number) != 0 || (box[boxn] & number) != 0) {
        
                        return false;
                    } else {
        
                        row[i] |= number;
                        col[j] |= number;
                        box[boxn] |= number;
                    }
                }
            }
            return true;
        }
    
    }

![在这里插入图片描述][b03bd5096259409ba00c43e20349c7de.png]

[36.]: https://leetcode.cn/problems/valid-sudoku/
[4b7dd69883e840b3a892395ee24d2c2c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/a0efa63100e6472a827881297825fb31.png
[a7b226ed5a9841748964047d4fd84e17.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/818864640fc64fd4bcbb193d48c60a89.png
[9bb8d0267ec64146b49660d340f8e8ca.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/06a3881f5ecd4272ba34894381841dcc.png
[760e6ab6c12b4370960f1709f14a98b8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/8025c565e7f8432195b88b40b7613cf4.png
[b03bd5096259409ba00c43e20349c7de.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/57f42dac696948d682f78a2dd8d19791.png