題目鏈接：Valid Sudoku有效的數(shù)獨(dú)

題目已經(jīng)十分確定的說了只有1~9，因此標(biāo)記法無疑是非常好的選擇。

基本思路：對(duì)行、列、小數(shù)獨(dú)塊分別用一個(gè)size為9的數(shù)組來標(biāo)記數(shù)字1~9在本行（列/塊）中是否已使用。

根據(jù)思路則不難寫出下面的代碼：

public static int startIndex = 0;public static int sudokuSize = 9;public boolean isValidSudoku(char[][] board) {int i;boolean[][] mark = new boolean[sudokuSize][sudokuSize+1];// 判斷所有行是否符合for (i = startIndex; i < sudokuSize; i++) {for (int j = startIndex; j < sudokuSize; j++) {if (board[i][j] != '.') {int temp = board[i][j] - '0';if (mark[i][temp]) return false;else mark[i][temp] = true;}}}// 判斷所有列是否符合initMarkArr(mark, false);for (i = startIndex; i < sudokuSize; i++) {for (int j = startIndex; j < sudokuSize; j++) {if (board[j][i] != '.') {int temp = board[j][i] - '0';if (mark[i][temp]) return false;else mark[i][temp] = true;}}}// 判斷所有小數(shù)獨(dú)塊是否符合initMarkArr(mark, false);for (i = startIndex; i < sudokuSize; i++) {for (int j = startIndex; j < sudokuSize; j++) {int index = i/3 * 3 + j/3;if (board[j][i] != '.') {int temp = board[j][i] - '0';if (mark[index][temp]) return false;else mark[index][temp] = true;}}}return true;}// 初始化數(shù)組public void initMarkArr(boolean[][] arr, boolean value) {for (int j = 0; j < arr.length; j++) {Arrays.fill(arr[j], value);}}

代碼看起來有點(diǎn)冗余，我們稍作代碼簡(jiǎn)化，可得如下代碼

? ? public boolean isValidSudoku(char[][] board) {boolean[][] markRow = new boolean[9][10];boolean[][] markCol = new boolean[9][10];boolean[][] markBlock = new boolean[9][10];// 多定義兩個(gè)數(shù)組可以省去初始化操作for (int i = 0; i < 9; i++) {for (int j = 0; j < 9; j++) {int index = i/3 * 3 + j/3;if (board[j][i] != '.') {int temp = board[j][i] - '0';if (markRow[j][temp]) return false;else markRow[j][temp] = true;if (markCol[i][temp]) return false;else markCol[i][temp] = true;if (markBlock[index][temp]) return false;else markBlock[index][temp] = true;}}}return true;}

對(duì)于此題，似乎沒法靠?jī)?yōu)化算法來提升效率，硬要優(yōu)化的話，可以在位運(yùn)算上下點(diǎn)功夫。

? ? public boolean isValidSudoku(char[][] board) {int[][] mark = new int[3][9];for (int i = 0; i < 9; i++) {for (int j = 0; j < 9; j++) {int index = i/3 * 3 + j/3;if (board[j][i] != '.') {// 1左移？位，數(shù)獨(dú)中最大數(shù)為9，2^8大大小于int的maxint temp = 1 << (board[j][i] - '1');// 判斷每列是否出現(xiàn)重復(fù)用temp，否則|上tempif ((mark[0][j] & temp) > 0) return false;else mark[0][j] |= temp;// 每行if ((mark[1][i] & temp) > 0) return false;else mark[1][i] |= temp;//每塊if ((mark[2][index] & temp) > 0) return false;else mark[2][index] |= temp;}}}return true;}

進(jìn)一步簡(jiǎn)化代碼

? ? public boolean isValidSudoku(char[][] board) {int[][] mark = new int[3][9];for (int i = 0; i < 9; i++) {for (int j = 0; j < 9; j++) {int index = i/3 * 3 + j/3;if (board[j][i] != '.') {int temp = 1 << (board[j][i] - '1');if ((mark[0][j] & temp) > 0 || (mark[1][i] & temp) > 0 || (mark[2][index] & temp) > 0) return false;mark[0][j] |= temp;mark[1][i] |= temp;mark[2][index] |= temp;}}}return true;}

總結(jié)

以上是生活随笔為你收集整理的leetcode之Valid Sudoku有效的数独（一步步改进代码）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。