[Leetcode]36 Valid Sudoku

zhichangterry 發布于2019-08-14 14:54 / 2464人閱讀

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

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.

坐標轉換

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

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

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

代碼

// 關鍵是如何將坐標轉換成在每一個小的九宮格；
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;
}

云服務器 GPU云服務器 sudoku LeetCode Valid valid?file

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/65173.html

leetcode36 Valid Sudoku 查看數獨是否合法

摘要：如果重復則不合法，否則極為合法。在這里我們使用數組代替作為存儲行列和小正方形的值得數據結構。我存儲這所有的行列小正方形的情況，并判斷當前值是否重復。外循環則代表對下一行，下一列和下一個小正方形的遍歷。題目要求 Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules. The Sudoku boa...

wing324 2019-08-16 10:32 評論0 收藏0
leetcode 36 Valid Sudoku

摘要：要求我們判斷已經填入的數字是否滿足數獨的規則。即滿足每一行每一列每一個粗線宮內的數字均含，不重復。沒有數字的格子用字符表示。通過兩層循環可以方便的檢查每一行和每一列有沒有重復數字。對于每個，作為縱坐標，作為橫坐標。題目詳情 Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.The Sudo...

entner 2019-08-15 14:51 評論0 收藏0
leetcode 部分解答索引（持續更新～）

摘要：前言從開始寫相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫現在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言從開始寫leetcode相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫～現在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理 1~50 1...

leo108 2019-08-15 14:26 評論0 收藏0
[LeetCode] 37. Sudoku Solver

Problem Write a program to solve a Sudoku puzzle by filling the empty cells. A sudoku solution must satisfy all of the following rules: Each of the digits 1-9 must occur exactly once in each row.Each ...

alaege 2019-08-19 11:14 評論0 收藏0
leetcode37 Sudoku Solver

摘要：題目要求也就是給出一個解決數獨的方法，假設每個數獨只有一個解決方案。并將當前的假象結果帶入下一輪的遍歷之中。如果最終遍歷失敗，則逐級返回，恢復上一輪遍歷的狀態，并填入下一個合理的假想值后繼續遍歷。題目要求 Write a program to solve a Sudoku puzzle by filling the empty cells. Empty cells are indi...

pepperwang 2019-08-15 10:49 評論0 收藏0