leetcode36 Valid Sudoku 查看數(shù)獨(dú)是否合法

wing324 發(fā)布于2019-08-16 10:32 / 540人閱讀

摘要：如果重復(fù)則不合法，否則極為合法。在這里我們使用數(shù)組代替作為存儲(chǔ)行列和小正方形的值得數(shù)據(jù)結(jié)構(gòu)。我存儲(chǔ)這所有的行列小正方形的情況，并判斷當(dāng)前值是否重復(fù)。外循環(huán)則代表對(duì)下一行，下一列和下一個(gè)小正方形的遍歷。

題目要求

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.
The Sudoku board could be partially filled, where empty cells are filled with the character ".".
    
Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

一個(gè)數(shù)獨(dú)合法的標(biāo)準(zhǔn)如下

每一行每一列必須包含1-9之間的每一個(gè)數(shù)字（包括1和9）

每一個(gè)小的正方形矩陣中必須包含1-9之間的每一個(gè)數(shù)字（包括1和9）

所以總體思路就是遍歷數(shù)獨(dú)，判斷行、列以及每一個(gè)小的正方形中的數(shù)字是否合法

如圖所示的數(shù)獨(dú)就是一個(gè)合法的數(shù)獨(dú)

思路一：使用StringBuilder API

假設(shè)我們持有已經(jīng)遍歷過(guò)的小方格所在的行列以及正方形的所有值，那么我們只需要判斷當(dāng)前值在自己所在的行、列和小正方形是否有重復(fù)。如果重復(fù)則不合法，否則極為合法。
在這里我們使用StringBuilder數(shù)組代替Map作為存儲(chǔ)行列和小正方形的值得數(shù)據(jù)結(jié)構(gòu)。我們只需要利用StringBuilder的API來(lái)判斷當(dāng)前的值是否有重復(fù)即可。

注：如果字符串在新建以后被更改的可能性較大，建議不要使用String而是使用StringBuilder，可以明顯提高效率

代碼如下

    public boolean isValidSudoku(char[][] board) {
        //9個(gè)StringBuilder分別代表9個(gè)小正方形
        StringBuilder[] squares = new StringBuilder[]{new StringBuilder(""),new StringBuilder(""),new StringBuilder(""),new StringBuilder(""),new StringBuilder(""),new StringBuilder(""),new StringBuilder(""),new StringBuilder(""),new StringBuilder("")};
        //9列
        StringBuilder[] columns = new StringBuilder[]{new StringBuilder(""),new StringBuilder(""),new StringBuilder(""),new StringBuilder(""),new StringBuilder(""),new StringBuilder(""),new StringBuilder(""),new StringBuilder(""),new StringBuilder("")};
        //當(dāng)前行
        StringBuilder line;
        for(int i = 0 ; i
思路二：利用下標(biāo)
上一個(gè)方法的思路是相當(dāng)直觀的。我存儲(chǔ)這所有的行列小正方形的情況，并判斷當(dāng)前值是否重復(fù)。但是，很明顯我們并不需要一直關(guān)注所有的行和列，這樣當(dāng)我們關(guān)注某一行或者某一列時(shí)，無(wú)需存儲(chǔ)其他的行列或是小正方形的值。所以我們轉(zhuǎn)而利用二重循環(huán)的下標(biāo)來(lái)表示行、列和小正方形，減少不必要的數(shù)據(jù)存儲(chǔ)，每一次內(nèi)循環(huán)都代表著對(duì)一行或是一列或是一個(gè)小正方形的遍歷。外循環(huán)則代表對(duì)下一行，下一列和下一個(gè)小正方形的遍歷。
代碼如下：
    public boolean isValidSudoku(char[][] board) {
        for(int i = 0; i<9; i++){
            HashSet rows = new HashSet();
            HashSet columns = new HashSet();
            HashSet cube = new HashSet();
            for (int j = 0; j < 9;j++){
                if(board[i][j]!="." && !rows.add(board[i][j]))
                    return false;
                if(board[j][i]!="." && !columns.add(board[j][i]))
                    return false;
                int RowIndex = 3*(i/3);
                int ColIndex = 3*(i%3);
                if(board[RowIndex + j/3][ColIndex + j%3]!="." && !cube.add(board[RowIndex + j/3][ColIndex + j%3]))
                    return false;
            }
        }
        return true;
                
    }

想要了解更多開(kāi)發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~