[Leetcode]36 Valid Sudoku

zhichangterry 發(fā)布于2019-08-14 14:54 / 2474人閱讀

摘要：的可以由確定，這一點(diǎn)在里面的位置可以由確定所以每確定一行，每一個值都可以被轉(zhuǎn)換到一個之中。如果允許的空間復(fù)雜度，可以設(shè)置一個二維數(shù)組來用來判斷是否在里重現(xiàn)了重復(fù)的數(shù)字。將一個數(shù)字的每一個位上表示每一個數(shù)字。

Leetcode[36] Valid Sudoku

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.

坐標(biāo)轉(zhuǎn)換

復(fù)雜度
時間復(fù)雜度 O(MN) 空間復(fù)雜度 O(1)

思路
對于boardi上的一點(diǎn)，要滿足這一點(diǎn)所在的行，所在的列，和這一點(diǎn)所在的block里有且只有這一個數(shù)。首先考慮，如何找到這一點(diǎn)對應(yīng)的block。block的index可以由(i / 3) 3 + j / 3確定，這一點(diǎn)在block里面的位置可以由(i % 3) 3 + j % 3確定. 所以每確定一行，每一個值都可以被轉(zhuǎn)換到一個block之中。

如果允許O(N)的空間復(fù)雜度，可以設(shè)置一個二維數(shù)組9*9來用來判斷是否在block里重現(xiàn)了重復(fù)的數(shù)字。如果用O(1)的空間復(fù)雜度，可以用bitset的方式。將一個數(shù)字的每一個bit位上表示每一個數(shù)字。通過將set和新來的數(shù)字相與，可以知道這個數(shù)字是否之前出過。

代碼

// 關(guān)鍵是如何將坐標(biāo)轉(zhuǎn)換成在每一個小的九宮格；
public boolean isValidSudoku(char[][] board) {
    for(int i = 0; i < 9; i ++) {
        // set bitmap for row, col and block.
        int row = 0;
        int col = 0;
        int block = 0;
        for(int j = 0; j < 9; j ++) {
            int rowval = board[i][j] - "1";
            int colval = board[j][i] - "1";
            int blockval = board[i / 3 * 3 + j / 3][i % 3 * 3 + j % 3] - "1";
            // 將值移動每一個bit位上，來判斷是否相等。
            if(rowval >= 0 && (row & (1 << rowval)) != 0
            || colval >= 0 && (col & (1 << colval)) != 0
            || blockval >= 0 && (block & (1 << blockval)) != 0) return false;
            row |= 1 << rowval;
            col |= 1 << colval;
            block |= 1 << blockval;
        }
    }
    return true;
}