程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> leetCode 36.Valid Sudoku(有效的數獨) 解題思路和方法

leetCode 36.Valid Sudoku(有效的數獨) 解題思路和方法

編輯:關於C++
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 '.'.
\
A partially filled sudoku which is valid.

Note:

A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

 

思路:題目很簡單,主要是規則的理解,數獨的游戲沒有玩過,不知道什麼規則,我以為任意9個方格1-9的個數都至多為1,誰知規則是特定的九個格內1-9的個數至多為1,其他不考慮。代碼比較啰嗦,但思路清晰,如下:

 

public class Solution {
    //置為靜態變量
    static Map map = new HashMap();
    public boolean isValidSudoku(char[][] board) {
        //判斷每行
        for(int i = 0; i < board.length; i++){
            initMap();//每次均需初始化
            for(int j = 0; j < board[0].length; j++){
                //是數字
                if(board[i][j] >= '0' && board[i][j] <= '9'){
                    if(map.get(board[i][j]) > 0){//說明重復數字
                        return false;
                    }else{
                        map.put(board[i][j],1);
                    }
                }else if(board[i][j] != '.'){//出現空格和0-9之外的字符
                    return false;//直接返回false
                }
            }
        }
        //判斷每列
        for(int i = 0; i < board[0].length; i++){
            initMap();//每次均需初始化
            for(int j = 0; j < board.length; j++){
                //是數字
                if(board[j][i] >= '0' && board[j][i] <= '9'){
                    if(map.get(board[j][i]) > 0){//說明重復數字
                        return false;
                    }else{
                        map.put(board[j][i],1);
                    }
                }else if(board[j][i] != '.'){//出現空格和0-9之外的字符
                    return false;//直接返回false
                }
            }
        }
        //判斷九宮格
        for(int i = 0; i < board.length - 2; i = i+3){//行{
            for(int j = 0; j < board[0].length - 2; j=j+3){
                initMap();//初始化
                for(int m = i; m < i + 3;m++){
                    for(int n = j; n < j+3; n++){
                        //是數字
                        if(board[m][n] >= '0' && board[m][n] <= '9'){
                            if(map.get(board[m][n]) > 0){//說明重復數字
                                return false;
                            }else{
                                map.put(board[m][n],1);
                            }
                        }else if(board[m][n] != '.'){//出現空格和0-9之外的字符
                            return false;//直接返回false
                        }
                    }
                }
            }
        }
        return true;
    }
    //初始化map為每個key均賦值0
    private void initMap(){
        for(char i = '0';i <= '9'; i++){
            map.put(i,0);
        }
    }
}


 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved