本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer，已开源在github ，欢迎star！
36. 有效的数独
本题来自LeetCode：36. 有效的数独[1]
题目描述
判断一个 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 形式的。
题目分析
每个非空白格，受到三个方面的约束：
题目解答
class Solution {
// 行数字掩码
private int[] rowMasks = new int[9];
// 列数字掩码
private int[] columnMasks = new int[9];
// 3x3宫数字掩码
private int[][] masks_3x3 = new int[3][3];
public boolean isValidSudoku(char[][] board) {
for(int i = 0; i 9; i ++) {
for(int j = 0; j 9; j ++) {
if(board[i][j] != '.') {
int bitMask = 1 (board[i][j] - '0');
// 该行已经包含该数
if((rowMasks[i] & bitMask) == bitMask) {
return false;
}
rowMasks[i] ^= bitMask;
// 该列已经包含该数
if((columnMasks[j] & bitMask) == bitMask) {
return false;
}
columnMasks[j] ^= bitMask;
// 该3x3宫已经包含该数
if((masks_3x3[i/3][j/3] & bitMask) == bitMask) {
return false;
}
masks_3x3[i/3][j/3] ^= bitMask;
}
}
}
return true;
}
}
复杂度分析：
时间复杂度：
O(1)
空间复杂度：
O(1)
37. 解数独
本题来自LeetCode：37. 解数独[2]
题目描述
编写一个程序，通过已填充的空格来解决数独问题。
一个数独的解法需遵循如下规则：
数字
1-9在每一行只能出现一次。
数字
1-9在每一列只能出现一次。
数字
1-9在每一个以粗实线分隔的
3x3宫内只能出现一次。
空白格用
'.'表示。
一个数独。
答案被标成红色。
Note:
给定的数独序列只包含数字
1-9和字符
'.' 。
你可以假设给定的数独只有唯一解。
给定数独永远是
9x9形式的。
题目分析
每个空白格的可能值，受到三个方面的约束：
我们可以对上面三种情况求交集，就可以得到该空白格的可用数字了。实际处理中，我们可以通过求出三个情况已占用数字的并集，然后求出与
1...9的差集，就可以得到可用的数字了。
本题可以采用回溯法来解答，具体解答过程，直接看实现。
题目解答
class Solution {
// 行数字掩码
private int[] rowMasks = new int[9];
// 列数字掩码
private int[] columnMasks = new int[9];
// 3x3宫数字掩码
private int[][] masks_3x3 = new int[3][3];
public void solveSudoku(char[][] board) {
initMasks(board);
// 按从左到右、从上到下的顺序，给各单元格编号
// 从位置0开始，处理0...80位置的单元格
backtracing(0, board);
}
// 回溯法，填充数独的空白格
public boolean backtracing(int index, char[][] board) {
// 表示所有单元格全部处理完了
if(index == 81) {
return true;
}
// 计算出该单元格的实际行
int m = index / 9;
// 计算出该单元格的实际列
int n = index % 9;
char c = board[m][n];
// 若该位置原来就有数字，则直接处理下一个位置
if(!isEmpty(c)) {
return backtracing(index + 1, board);
}
// 计算出该单元格已经被占用的数字掩码
int oxr = rowMasks[m] | columnMasks[n] | masks_3x3[m/3][n/3];
// 遍历1...9，找到该单元格可用的数字
for(int i = 1; i = 9; i ++) {
int bitMask = 1 i;
// 表是该数字不可用
if((oxr & bitMask) != 0) {
continue;
}
// 将board[m][n]位置填充为i，并设置相关掩码
rowMasks[m] |= bitMask;
columnMasks[n] |= bitMask;
masks_3x3[m/3][n/3] |= bitMask;
board[m][n] = (char)(i + '0');
if(backtracing(index + 1, board)) {
return true;
}
// 表示board[m][n]=i，不是有效的解，将掩码及board[m][n]还原
rowMasks[m] ^= bitMask;
columnMasks[n] ^= bitMask;
masks_3x3[m/3][n/3] ^= bitMask;
board[m][n] = '.';
}
return false;
}
// 初始化各掩码
public void initMasks(char[][] board) {
for(int i = 0; i 9; i ++) {
for(int j = 0; j 9; j ++) {
if(!isEmpty(board[i][j])) {
int bitMask = getBitMask(board[i][j]);
rowMasks[i] ^= bitMask;
columnMasks[j] ^= bitMask;
masks_3x3[i/3][j/3] ^= bitMask;
}
}
}
}
// 获取字符数字的掩码
public int getBitMask(char c) {
return 1 (c - '0');
}
// 是否为空白格
public boolean isEmpty(char c) {
return c == '.';
}
}
复杂度分析：
时间复杂度：这个暂不知道怎么算。。。
空间复杂度：
O(1)，回溯法空架复杂度最多为
81，
参考资料
原文始发于微信公众号（xiaogan的技术博客）：
