leetcode36 Valid Sudoku 查看数独是否合法

wing324 发布于2019-08-16 10:32 / 514人阅读

摘要：如果重复则不合法，否则极为合法。在这里我们使用数组代替作为存储行列和小正方形的值得数据结构。我存储这所有的行列小正方形的情况，并判断当前值是否重复。外循环则代表对下一行，下一列和下一个小正方形的遍历。

题目要求

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 查看域名是否到期查看域名是否过期

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

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