leetcode36 Valid Sudoku 查看數獨是否合法

wing324 發布于2019-08-16 10:32 / 530人閱讀

摘要：如果重復則不合法，否則極為合法。在這里我們使用數組代替作為存儲行列和小正方形的值得數據結構。我存儲這所有的行列小正方形的情況，并判斷當前值是否重復。外循環則代表對下一行，下一列和下一個小正方形的遍歷。

題目要求

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.

一個數獨合法的標準如下

每一行每一列必須包含1-9之間的每一個數字（包括1和9）

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

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

如圖所示的數獨就是一個合法的數獨

思路一：使用StringBuilder API

假設我們持有已經遍歷過的小方格所在的行列以及正方形的所有值，那么我們只需要判斷當前值在自己所在的行、列和小正方形是否有重復。如果重復則不合法，否則極為合法。
在這里我們使用StringBuilder數組代替Map作為存儲行列和小正方形的值得數據結構。我們只需要利用StringBuilder的API來判斷當前的值是否有重復即可。

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

代碼如下

    public boolean isValidSudoku(char[][] board) {
        //9個StringBuilder分別代表9個小正方形
        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("")};
        //當前行
        StringBuilder line;
        for(int i = 0 ; i
思路二：利用下標
上一個方法的思路是相當直觀的。我存儲這所有的行列小正方形的情況，并判斷當前值是否重復。但是，很明顯我們并不需要一直關注所有的行和列，這樣當我們關注某一行或者某一列時，無需存儲其他的行列或是小正方形的值。所以我們轉而利用二重循環的下標來表示行、列和小正方形，減少不必要的數據存儲，每一次內循環都代表著對一行或是一列或是一個小正方形的遍歷。外循環則代表對下一行，下一列和下一個小正方形的遍歷。
代碼如下：
    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;
                
    }

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

GPU云服務器云服務器是否合法 sudoku 查看域名是否到期查看域名是否過期

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

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

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]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
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
LeetCode 攻略 - 2019 年 8 月上半月匯總（109 題攻略）

摘要：每天會折騰一道及以上題目，并將其解題思路記錄成文章，發布到和微信公眾號上。三匯總返回目錄在月日月日這半個月中，做了匯總了數組知識點。或者拉到本文最下面，添加的微信等會根據題解以及留言內容，進行補充，并添加上提供題解的小伙伴的昵稱和地址。 LeetCode 匯總 - 2019/08/15 Create by jsliang on 2019-08-12 19:39:34 Recently...

tracy 2019-08-26 10:49 評論0 收藏0
LeetCode36.有效的數獨 JavaScript

摘要：上圖是一個部分填充的有效的數獨。數獨部分空格內已填入了數字，空白格用表示。但由于位于左上角的宮內有兩個存在因此這個數獨是無效的。說明一個有效的數獨部分已被填充不一定是可解的。只需要根據以上規則，驗證已經填入的數字是否有效即可。判斷一個 9x9的數獨是否有效。只需要根據以下規則，驗證已經填入的數字是否有效即可。數字 1-9 在每一行只能出現一次。數字 1-9 在每一列只能出現一次...

elva 2019-08-23 15:16 評論0 收藏0