leetcode 36 Valid Sudoku

entner 发布于2019-08-15 14:51 / 1097人阅读

摘要：要求我们判断已经填入的数字是否满足数独的规则。即满足每一行每一列每一个粗线宫内的数字均含，不重复。没有数字的格子用字符表示。通过两层循环可以方便的检查每一行和每一列有没有重复数字。对于每个，作为纵坐标，作为横坐标。

题目详情

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

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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