leetCode 36.Valid美高梅59599: Sudoku(有效的数独) 解题思路和方法

leetCode 36.Valid美高梅59599: Sudoku(有效的数独) 解题思路和方法

LeetCode36: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 '.'.

美高梅59599 1

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.

 

这道题一看就是用空间来换取时间,正常情况下应该每行进行比较,每列进行比较,然后每一个网格进行比较,但是每个比较都有一个双层循环。

可以借助STL中的set来进行判断是否已经存在该元素,典型的空间换取时间的方法。

runtime:24ms

 

class Solution {
public:
    bool isValidSudoku(vector>& board) {
        unordered_set rows[9];//每一行一个set来判断改行是否存在重复元素
        unordered_set columns[9];//每一列一个set用来判断该列是否存在重复元素
        unordered_set grids[3][3];//每一个3*3网格一个set来判断该网格是否存在重复元素
        for(int i=0;i<9;i++)
        {
            for(int j=0;j<9;j++)
            {
                if(board[i][j]!='.')
                {
                    char tmp=board[i][j];
                    if(!rows[i].insert(tmp).second||!columns[j].insert(tmp).second||!grids[i/3][j/3].insert(tmp).second)
                    return false;

                }
            }

        }
        return true;

    }
};

除了使用STL外由于这道题比较简单,可以使用和上面同样的方式自己定义一个掩码。

 

用一个int rows[9][9]来记录行的掩码

用一个int column[9][9]来记录列的掩码

用一个int gird[3][3][9]来记录网格的掩码。

runtime:12ms

运行时间少了一半!!!!

 

class Solution {
public:  
       bool isValidSudoku(vector>& board) {
             int rows[9][9]={0};
             int columns[9][9]={0};
             int grids[3][3][9]={0};

            for(int i=0;i<9;i++)
            {
                for(int j=0;j<9;j++)
                {
                    if(board[i][j]!='.')
                    {
                           char tmp=board[i][j];
                           int index=tmp-'1';

                           if(rows[i][index]++)
                               return false;

                           if(columns[j][index]++)
                                return false;

                            if(grids[i/3][j/3][index]++)
                                return false;  
                    }

                }
            }
            return true;

        }


};

 

 

http://www.bkjia.com/cjjc/1015552.htmlwww.bkjia.comtruehttp://www.bkjia.com/cjjc/1015552.htmlTechArticleLeetCode36: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…

leetCode 36.Valid Sudoku(有效的数独) 解题思路和方法

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 ‘.’.
美高梅59599 2
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);
        }
    }
}

 

 

http://www.bkjia.com/cjjc/1029730.htmlwww.bkjia.comtruehttp://www.bkjia.com/cjjc/1029730.htmlTechArticleleetCode 36.Valid Sudoku(有效的数独)
解题思路和方法 Valid Sudoku Determine if a Sudoku is valid, according
to: Sudoku Puzzles – The Rules. The Sudoku board could be par…

admin

网站地图xml地图