389.Valid Sudoku-判断数独是否合法（容易题）

本文主要是介绍389.Valid Sudoku-判断数独是否合法（容易题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

判断数独是否合法

1. 题目

   请判定一个数独是否有效。
   该数独可能只填充了部分数字，其中缺少的数字用 . 表示。

   注意事项
   一个合法的数独（仅部分填充）并不一定是可解的。我们仅需使填充的空格有效即可。

2. 说明

   什么是 数独？
   http://sudoku.com.au/TheRules.aspx
   http://baike.baidu.com/subview/961/10842669.htm

3. 样例

   下列就是一个合法数独的样例。
   

4. 题解

1.最笨的解法，先检查行列，再查每一个小的九宫格。时间复杂度为O(N^3)。

class Solution {/*** @param board: the board @return: wether the Sudoku is valid*/public boolean isValidSudoku(char[][] board) {int n = 9;char[] array = new char[n];//先检查横向的for (int i=0;i<n;i++){if (!check(board[i])){return false;}}//再检查纵向的for (int i=0;i<n;i++){for (int j=0;j<n;j++){array[j] = board[j][i];}if (!check(array)){return false;}}//最后检查每个九宫格for (int i=0;i<n;i+=3){for (int j=0;j<n;j+=3){for (int k=0;k<n;k++){array[k] = board[i+k/3][j+k%3];}}if (!check(array)){return false;}}return true;}public boolean check(char[] array){for (int i=0;i<array.length;i++){if (array[i] != '.'){for (int j=i+1;j<array.length;j++){if (array[j] != '.' && array[i] == array[j]){return false;}}}}return true;}
};

2.用HashMap判断是否有数字重复，只需将矩阵遍历一次即可。
简单说下思路，对数独矩阵进行遍历，将数字的坐标(i,j)存入HashMap的Point列表中，如果在遍历到某个数字时发现对应的ArrayList中已经有相同的数字存在了则进行判断是否导致数独非法，判断方式如下：
a.两个数字同行；
b.两个数字同列；
c.两个数字同在一个小九宫格；
其中a,b很容易，c稍微有些麻烦，我是采用下面的方法判断的。
由于只需判断两个数字同在一个小九宫格即可，无需知道具体的位置。所以首先将列表中已存在的那个数字k的坐标调整至其所处九宫格的左上角（代码如下），以进行简化处理，那么当前遍历的数字p与k同在一个九宫格，那么p的坐标i,j必然大于k的新坐标x,y，且差不大于2。

int x = (points.get(k).x / 3) * 3;
int y = (points.get(k).y / 3) * 3;

class Solution {/*** @param board: the board @return: wether the Sudoku is valid*/public boolean isValidSudoku(char[][] board) {final int n = 9;HashMap<Integer,ArrayList<Point>> hash = new HashMap<>();ArrayList<Point> points = null;for (int i = 0; i < n;i++){for (int j = 0; j < n; j++){if (board[i][j] != '.'){Point p = new Point(i,j);int val = board[i][j];points = hash.get(val) != null ? hash.get(val):new ArrayList<Point>();for (int k = 0; k < points.size(); k++){int x = (points.get(k).x / 3) * 3;int y = (points.get(k).y / 3) * 3;if (points.get(k).x == p.x || points.get(k).y == p.y || ((p.x - x <= 2) && p.x >= x) && ((p.y - y <= 2) && p.y >= y)){return false;}}points.add(p);hash.put(val,points);}}}return true;}
};

Last Update 2016.9.14

这篇关于389.Valid Sudoku-判断数独是否合法（容易题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---