leetcode 36 Valid Sudoku

entner 發布于2019-08-15 14:51 / 1122人閱讀

摘要：要求我們判斷已經填入的數字是否滿足數獨的規則。即滿足每一行每一列每一個粗線宮內的數字均含，不重復。沒有數字的格子用字符表示。通過兩層循環可以方便的檢查每一行和每一列有沒有重復數字。對于每個，作為縱坐標，作為橫坐標。

題目詳情

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 ".".

輸入一個二維數組表示的數獨版(board)。要求我們判斷已經填入的數字是否滿足數獨的規則。即滿足每一行、每一列、每一個粗線宮（3*3）內的數字均含1-9，不重復。沒有數字的格子用字符"."表示。

例如：

想法

這道題沒有什么陷阱，主要的想法就是檢查每一行現有的元素、每一列現有的元素、每一個粗線宮里的現有元素有沒有重復。

麻煩一點的解法就是我們用三次遍歷分別檢查每一行、每一列、每個粗線宮。但是這樣代碼比較復雜比較ugly，但是好理解呀～

另一種簡潔的想法把三種判斷在一次遍歷中完成。

通過兩層循環可以方便的檢查每一行和每一列有沒有重復數字。那我們如何遍歷每個粗線宮呢？

因為臨時變量j的取值是從0-9，我們可以用"/"和"%"兩個操作符來代替完成遍歷粗線宮的行為。

j/3的值作為縱坐標的增量，j％3的值作為橫坐標的增量。

這樣對于一個粗線宮的左上角頂點來說，j從0～9就可以完成對于整個粗線宮的遍歷。

然后我們仍需要確定每一個粗線宮的頂點。

對于每個i，(i/3)3作為縱坐標，(i%3)3作為橫坐標。這樣對于i從0～9，我們可以取到每一個粗線宮的左上角了。

解法

簡潔版～

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;
}

復雜點～～

    public boolean isValidSudoku(char[][] board) {
        boolean res = true;
        int length = 9;
        
        //判斷行
        for(int i=0;i temp = new HashSet();
            for(char c : board[i]){
                if(c != "."){
                    if(!temp.add(c)){
                        return false;
                    }
                }
            }
        }
        
        //判斷列
        for(int i=0;i temp = new HashSet();
            for(int j=0;j temp = new HashSet();
            for(int[] direct : directs){
                char c =board[direct[0]+a[0]][direct[1]+a[1]];
                if(c != "."){
                    if(!temp.add(c)){
                        return false;
                    }
                }  
            }
        }

        
        return res;
    }

GPU云服務器云服務器 sudoku Leetcod Valid LeetCode

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

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

[Leetcode]36 Valid Sudoku

摘要：的可以由確定，這一點在里面的位置可以由確定所以每確定一行，每一個值都可以被轉換到一個之中。如果允許的空間復雜度，可以設置一個二維數組來用來判斷是否在里重現了重復的數字。將一個數字的每一個位上表示每一個數字。 Leetcode[36] Valid Sudoku Determine if a Sudoku is valid, according to: Sudoku Puzzles - ...

zhichangterry 2019-08-14 14:54 評論0 收藏0
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 部分解答索引（持續更新～）

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