leetcode算法练习【37】 解数独git椰子奶糖的博客-

所有题目源代码：Git地址

题目

编写一个程序，通过已填充的空格来解决数独问题。  一个数独的解法需遵循如下规则：  数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 空白格用 '.' 表示。  

• 一个数独。

答案被标成红色。  Note:  给定的数独序列只包含数字 1-9 和字符 '.' 。 你可以假设给定的数独只有唯一解。 给定数独永远是 9x9 形式的。 

方案：回朔法

• 思路比较简单：每走一格就判断是否存在满足条件的数，如果没有，那么就回朔上一格，有则走下一格
• 这边为了偷懒用了三个HashMap存放每行、列、块已用过的数，用别的数据结构也可以达到同样的效果，而且应该会更优，我这个是懒得改了。
• 顺手封装了几个方法优化了下结构，刚写完的时候这个代码结构真的没法看

class Solution { //27个hashmap，9个一组，分为横、竖、块 private HashMap<Character, Integer>[] col = new HashMap[9]; private HashMap<Character, Integer>[] row = new HashMap[9]; private HashMap<Character, Integer>[] chunk = new HashMap[9]; public void solveSudoku(char[][] board) { //1、读取原本存在的数，每一次读取都有三个hashMap需要放,遍历一遍即可 //  横着：  j+1 //  竖着：  i+1 //  块：    (j/3)*3+(i/3)+1 initHash(board); //2、回朔法：递归？如果此值满足取值条件但是走不下去，则返回取下一个值，取值范围就从小到大 recall(board, 0, 0); return; } public boolean recall(char[][] board, int rowstart, int colstart) { //如果该位置不为空 if (board[rowstart][colstart] != '.') { if (colstart == 8 && rowstart == 8) return true; else if (colstart == 8 && rowstart < 8) return recall(board, rowstart + 1, 0); else return recall(board, rowstart, colstart + 1); } else { //如果该位置为空 for (char i = '1'; i <= '9'; i++) { if (check(rowstart, colstart, i)) { putIntoHash(rowstart, colstart, i);                         board[rowstart][colstart] = i; //如果这个数可以，那么就进入 if (colstart == 8 && rowstart == 8) return true; else if (colstart == 8 && rowstart < 8) { if (recall(board, rowstart + 1, 0)) return true; } else if (recall(board, rowstart, colstart + 1)) return true; //如果不匹配，那就continue removeFromHash(board, rowstart, colstart, i); } } } return false; } public void initHash(char[][] board) { for (int i = 0; i < 9; i++) {                 row[i] = new HashMap<>( );                 col[i] = new HashMap<>( );                 chunk[i] = new HashMap<>( ); } for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { if (board[i][j] == '.') continue; else if (board[i][j] <= '9' && board[i][j] >= 1) { //位置中有数字，则添加                         row[i].put(board[i][j], 1);                         col[j].put(board[i][j], 1);                         chunk[(i / 3) * 3 + j / 3].put(board[i][j], 1); } } } } public void putIntoHash(int rowstart, int colstart, char target) {             row[rowstart].put(target, 1);             col[colstart].put(target, 1);             chunk[(rowstart / 3) * 3 + colstart / 3].put(target, 1); } public void removeFromHash(char[][] board, int rowstart, int colstart, char target) {             board[rowstart][colstart] = '.';             row[rowstart].remove(target);             col[colstart].remove(target);             chunk[(rowstart / 3) * 3 + colstart / 3].remove(target); } public boolean check(int i, int j, char target) { /**              * board 是数组              */ if (col[j].get(target) != null) return false; if (row[i].get(target) != null) return false; if (chunk[(i / 3) * 3 + j / 3].get(target) != null) return false; return true; } } 

复杂度计算：

• 时间复杂度：计算最坏情况是9⁸¹
• 空间复杂度：共有：8123个临时变量，也就是三个HashMap，也就是O(1)