LeetCode初级算法之数组：36.有效数独

有效数独

题目地址：https://leetcode-cn.com/problems/valid-sudoku/

判断一个 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

说明:

一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
给定数独序列只包含数字 1-9 和字符 ‘.’ 。
给定数独永远是 9×9 形式的。

暴力

最直观的也就是按照题目流程的暴力解法，需要去判断每行每列每块有没有重复，那就去拿到每行每列每块的二维数组。判断这三组二维数组中的每个一维数组是有否重复。这里举个类似的4×4的例子（图画的少一点）

比如：

row：
[
[‘1’，’2’，’3’，’4’],
[‘5’，’.’，’6’，’.’],
[‘.’，’7’，’8’，’.’],
[‘7’，’.’，’.’，’3’]
]

col：
[
[‘1’，’5’，’.’，’7’],
[‘2’，’.’，’7’，’.’],
[‘3’，’6’，’8’，’.’],
[‘4’，’.’，’.’，’3’]
]

box：
[
[‘1’，’2’，’5’，’.’],
[‘3’，’4’，’6’，’.’],
[‘.’，’7’，’7’，’.’],
[‘8’，’.’，’.’，’3’]
]

解法一

public boolean isValidSudoku(char[][] board) {
    //传入的board相当于就是row所以只需要初始化两个数组
    char[][] col = new char[9][9];
    char[][] box = new char[9][9];
    //1.拿到三个二维数组分别表示多行数组，多列数组以及多块数组
    for(int i = 0; i < 9; i++){
        for(int j = 0; j < 9; j++){
            col[j][i] = board[i][j];
            box[(i/3)*3 + j/3][(i%3)*3 + j%3] = board[i][j];
       	}
    }
    //2.遍历每个二维数组中的数组判断有无重复
    for(int i = 0; i < 9; i++){
        if(checkRepeat(board[i])){
            return false;
        }
        if(checkRepeat(col[i])){
            return false;
        }
        if(checkRepeat(box[i])){
            return false;
        }
    }
    return true;
}
/**
检测单数组是否重复
*/
public boolean checkRepeat(char[] arr){
    for(int i = 0; i < 9; i++){
        for(int j = i+1; j < 9; j++){
            if(arr[i] != '.' && arr[j] != '.')
            if(arr[i] == arr[j]){
                return true;
            }
        }
    }
    return false;
}

上面解法实际上存在一个问题就是我们存完二维数组之后，再使用遍历查重的方式对每个单数组进行查重。

1 2	col[j][i] = board[i][j]; box[(i/3)3 + j/3][(i%3)3 + j%3] = board[i][j];

也就是说在存这两个二维数组时只有只有第一个中括号的索引是有用的标记着是哪一列或者哪一块，但它是在一列(块/行)的哪个位置是无所谓的，因为最后单独用了单数组查重的方式(无论顺序怎么样只要是在一个容器，最后容器单独用方法判断是否有重)。在编码中第二个中括号写的索引只不过是保留了在面板上我们去数数的顺序，换成别的0-9不重复的也可以。

是否重复的关键也就是数值是否一样，是否是同一块(行/列)这些相同也就是无效数独，和在具体行(列/块)里面的哪个位置无关。也就可以这样写

解法二

public boolean isValidSudoku(char[][] board) {
    HashSet<String> set = new HashSet();
    //遍历存值
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            char num = board[i][j];
            if (num != '.') {
                int n = num - '0';
                int box_index = (i / 3 ) * 3 + j / 3;
                String row = n + "是第"+i+"行";
                String col = n + "是第"+j+"列";
                String box = n + "是第"+box_index+"块";
                if(!set.add(row) || !set.add(col) || !set.add(box)) return false;
            }
        }
    }
    return true;
}

其实这才是最直接的方式，也是效率最低的。

Hash表

根据上述情况第二层容器的索引没有意义，只用第一层容器的索引判断存到哪个第二层容器(块/列/行)最后对所有第二层容器查重所以才无关。那我这里我们可以用上第二层容器的索引或者key把它的索引变得有意义，也就是等同于值。这样值就与位置相关，再存时就可以判断重复与否。而不用先存完之后在单独遍历每个第二层容器。

解法三

public boolean isValidSudoku(char[][] board) {
    //初始化数组
    HashMap<Integer, Integer> [] rows = new HashMap[9];
    HashMap<Integer, Integer> [] columns = new HashMap[9];
    HashMap<Integer, Integer> [] boxes = new HashMap[9];
    //初始化hashmap
    for (int i = 0; i < 9; i++) {
      rows[i] = new HashMap<Integer, Integer>();
      columns[i] = new HashMap<Integer, Integer>();
      boxes[i] = new HashMap<Integer, Integer>();
    }

    //遍历存值
    for (int i = 0; i < 9; i++) {
    	for (int j = 0; j < 9; j++) {
        	char num = board[i][j];
        	if (num != '.') {
          		int n = (int)num;
          		int box_index = (i / 3 ) * 3 + j / 3;
				//以数值为key存下
          		rows[i].put(n, rows[i].getOrDefault(n, 0) + 1);
          		columns[j].put(n, columns[j].getOrDefault(n, 0) + 1);
          		boxes[box_index].put(n, boxes[box_index].getOrDefault(n, 0) + 1);

          		//判断当前（行、列、块）此值有木有重复
          		if (rows[i].get(n) > 1 || columns[j].get(n) > 1 || boxes[box_index].get(n) > 1)
            		return false;
        	}
    	}
    }
    return true;
}

按照上述解法存值标记key，通过key来判断有没有存过。同样也可以用数组实现用索引标记值和用key标记值是一样的并且效率上也会更快。因存的数值就是1-9，那就把9存到第九个也就是索引8。这样存进一个容器同一个数字就一定在同一个地方，通过值可以找到索引，通过索引又可以找到目前存的值。那么和map用key是一样的。都是做到用数值标记位置，那么同一个值即同一个地方在这个地方判断是否有重、

解法四

public boolean isValidSudoku(char[][] board) {
    //初始化数组
    char[][] rows = new char[9][9];
    char[][] columns = new char[9][9];
    char[][] boxes = new char[9][9];

    //遍历存值
    for (int i = 0; i < 9; i++) {
    	for (int j = 0; j < 9; j++) {
        	char num = board[i][j];
        	if (num != '.') {
          		int n = num - '0';
          		int box_index = (i / 3 ) * 3 + j / 3;
                //以数值为索引存下
          		if(rows[i][n - 1] == num) return false;
          		if(columns[j][n - 1] == num) return false;
          		if(boxes[box_index][n - 1] == num) return false;
                rows[i][n - 1] = num;
                columns[j][n - 1] = num;
                boxes[box_index][n - 1] = num;
        	}
    	}
    }
    return true;
}

两种解法同一个思路只是选取的数据结构不同，同样是使用值来标记位置，通过值就能查找位置。因此如果有同样的值就在同一个位置可以去判断。map是以值为key来实现，数组在此情景下因为数独盘面是9×9，里面的数字只能是1到9，所以数字如果是1就存在0位，是4就存在索引3的位置。通过值减一固定存的位置。

但上面数组解法仍是存在疏漏浪费了空间，通过遍历的一个数我拿到这个数找对应位置的数值是否和这个数相等。仔细想一想后面这一部分就是废话，我都存同一个索引或者同一个key了就是值相同，何必还去取再比较。只有两种情况这个地方没有存过那就是那就是null和当前值不同，然后存过后再有一个往这个索引或者key存那就是重复了不用比。因为索引和key就是值。因此改成boolean，没存过都是false，存了就是true，再存同一个地方时发现是true就是这个值已经存过这次是重复的

解法五（解法四优化）

public boolean isValidSudoku(char[][] board) {
    //初始化数组
    boolean[][] rows = new boolean[9][9];
    boolean[][] columns = new boolean[9][9];
    boolean[][] boxes = new boolean[9][9];

    //遍历存值
    for (int i = 0; i < 9; i++) {
    	for (int j = 0; j < 9; j++) {
        	char num = board[i][j];
        	if (num != '.') {
          		int n = num - '0';
          		int box_index = (i / 3 ) * 3 + j / 3;
                //以数值为索引取看是否设过值
          		if(rows[i][n - 1]) return false;
          		if(columns[j][n - 1]) return false;
          		if(boxes[box_index][n - 1]) return false;
                rows[i][n - 1] = true;
                columns[j][n - 1] = true;
                boxes[box_index][n - 1] = true;
        	}
    	}
    }
    return true;
}

有了解法四之后实际上是更加可以进行优化的，因为结果标记只存在是与否两种状态，那我们何不用0/1位。可以进一步减少空间那我们需要一个9位的数字用byte类型只有1字节8位少了，所以只能用尽量小的short类型2字节也就是16位我们只用低9位。

现在用9位的一个数字（忽略高位）代替之前的9个元素的数组，也就没有子数组了

先以一个4×4的面板数字1-4做例子

扫描到第一个元素1那么它首先是第0块，在第0块里存第0位（数值-1）。那么上一个解法是子数组把里面的第0个设为true。现在不是子数组而是一个4位数把个位设成1。如果数字是3也就是把第2位设为1（true）

//把第0位设为1
 0000
+   1
-------
 0001

//把第二位设为1
 0000
+ 100
-------
 0100

以前是数组，存一个9就找在这个数组索引8存下true，现在就是将1左移位运算8然后相加，同样是将一个值的第8位改为1。当前存的值是否是重复以前是判断这个地方是否已经是true，现在与num进行与运算看是不是0，比如存一个4，要存在第三位

//第三位没有值
 001000101
&     1000 
----------
 000000000

//第三位有值
 001001000
&     1000
----------
 000001000

解法六(解法五优化)

public boolean isValidSudoku(char[][] board) {
    //初始化数组
    short[] rows = new short[9];
    short[] columns = new short[9];
    short[] boxes = new short[9];

    //遍历存值
    for (int i = 0; i < 9; i++) {
    	for (int j = 0; j < 9; j++) {
            char num = board[i][j];
            if (num != '.') {
          	num =(char)(1 << (num - '0'));
          	int box_index = (i / 3 ) * 3 + j / 3;
                if((rows[i] & num) != 0) return false;
                if((columns[j] & num) != 0) return false;
                if((boxes[box_index] & num) != 0) return false;
                rows[i] += num;
                columns[j] += num;
                boxes[box_index] += num;
            }
    	}
    }
    return true;
}

总结

前部分算法都是抛开标记暴力判断，整理完信息然后才判断有没有重复信息。再之后通过值做第二层容器的索引或者key，同一个值如果是同一列（块/行）就会存到同一个地方进而利用了第二层容器索引后可以在存的过程就判断是否有重，在之后这同一种思路在数据结构上有慢慢更好的选择，最终达到一个最优解。