首页 > > 程序设计 > Java技术 >

LeetCode 36. 有效的数独

2020-04-03 16:12:38来源：博客园阅读 ()

LeetCode 36. 有效的数独

我的LeetCode：https://leetcode-cn.com/u/ituring/

我的LeetCode刷题源码[GitHub]：https://github.com/izhoujie/Algorithmcii

LeetCode 36. 有效的数独

题目

判断一个?9x9 的数独是否有效。只需要__根据以下规则__，验证已经填入的数字是否有效即可。

数字?1-9?在每一行只能出现一次。
数字?1-9?在每一列只能出现一次。
数字?1-9?在每一个以粗实线分隔的?3x3?宫内只能出现一次。

上图是一个部分填充的有效的数独。

数独部分空格内已填入了数字，空白格用?'.'?表示。

示例?1:

输入:
[
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
输出: true

示例?2:

输入:
[
? ["8","3",".",".","7",".",".",".","."],
? ["6",".",".","1","9","5",".",".","."],
? [".","9","8",".",".",".",".","6","."],
? ["8",".",".",".","6",".",".",".","3"],
? ["4",".",".","8",".","3",".",".","1"],
? ["7",".",".",".","2",".",".",".","6"],
? [".","6",".",".",".",".","2","8","."],
? [".",".",".","4","1","9",".",".","5"],
? [".",".",".",".","8",".",".","7","9"]
]
输出: false
解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。
     但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

说明:

一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
给定数独序列只包含数字?1-9?和字符?'.'?。
给定数独永远是?9x9?形式的。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-sudoku
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

这道题做出来是比较简单的，暴力来每行每竖每小宫格分别校验就可以了，这样看至少需要三次全扫描；
如何做到只扫描一遍就能完成呢？分析后可能发现比较难解决是小宫格的索引问题，其次如果要保存原始数据，应该需要
横竖小宫格共三个二维数组（或者set集合），但是我们只需要知道1-9这几个数字有还是没有以及只能有一个，对应到编码就是0和1，因此可以进一步压缩二维数组为一位数组，
每个数组的int的前9个bit位用来存储1-9是否出现过且仅出现过一次，综上，从需要三次扫描三个二维数组到一次扫描三个二维数组再到最后一次扫描一个一维数组，算法的效率提升是非常明显的；

思路1-三遍扫描，横竖小宫格各自作校验

步骤：

新建三个set对应横竖小宫格；
三次扫描分别校验横竖小宫格；

思路2-只扫描一次

只扫描一次的关键是定位小宫格的索引：
关键点小宫格的索引公式：（i/3）*3 + j/3;

可以这么理解：
- i/3表示第几行的小宫格，取值为0、1、2对应实际的第一、二、三行；
- （i/3）3表示第i/3的小宫格下标的的起始数字，比如第一行是从0开始，第二行是从3开始，第三行是从6开始；
- j/3表示所在行的第j/3个宫格，取值为0、1、2对应实际的第一、二、三个小宫格；
- （i/3）3 + j/3 组合起来就是：前半段表示小宫格的所在行及起始下标，后半段表示当前行的第几个小宫格，组合的所有可能值0、1、2、3、、4、5、6、7、8就对应九个小宫格；

思路3-只扫描一次，进一步压缩辅助空间，使用bit位记录数据

实际做法和代码与思路2无太大区别，唯一的区别是数组换位一维的，校验时使用位记录和对比校验；

算法源码示例

package leetcode;

import java.util.HashSet;

/**
 * @author ZhouJie
 * @date 2020年2月1日 下午4:30:05 
 * @Description: 36. 有效的数独
 *
 */
public class LeetCode_0036 {

}

class Solution_0036 {
	/**
	 * @author ZhouJie
	 * @date 2020年2月1日 下午8:27:14 
	 * @Description: TODO(方法简述) 
	 * @return boolean 
	 * @UpdateUser-UpdateDate:[ZhouJie]-[2020年2月1日 下午8:27:14]  
	 * @UpdateRemark:1-行列小宫格分别遍历校验，使用一个set
	 *
	 */
	public boolean isValidSudoku_1(char[][] board) {
		if (board == null) {
			return false;
		}
		HashSet<Character> set = new HashSet<Character>();
		// 行列判断
		for (int x = 0; x < 9; x++) {
			set.clear();
			// 行判断
			for (int y = 0; y < 9; y++) {
				if (!check(set, board[x][y])) {
					return false;
				}
			}
			set.clear();
			// 列判断
			for (int y = 0; y < 9; y++) {
				if (!check(set, board[y][x])) {
					return false;
				}
			}
		}
		// 小宫格判断，先定位单个小宫格位置，再遍历小宫格的数字
		for (int i = 0; i < 9; i += 3) {
			for (int j = 0; j < 9; j += 3) {
				set.clear();
				for (int x = 0; x < 3; x++) {
					for (int y = 0; y < 3; y++) {
						if (!check(set, board[x + i][y + j])) {
							return false;
						}
					}
				}
			}
		}
		return true;
	}

	private boolean check(HashSet<Character> set, char c) {
		if (c == '.') {
			return true;
		} else if (set.contains(c)) {
			return false;
		} else {
			set.add(c);
			return true;
		}
	}

	/**
	 * @author ZhouJie
	 * @date 2020年2月1日 下午8:27:38 
	 * @Description: TODO(方法简述) 
	 * @return boolean 
	 * @UpdateUser-UpdateDate:[ZhouJie]-[2020年2月1日 下午8:27:38]  
	 * @UpdateRemark:2-行列小宫格各自使用自己的校验空间同时校验，一次遍历 
	 *
	 */
	public boolean isValidSudoku_2(char[][] board) {
		// 行列小宫格的编号
		int[][] rows = new int[9][9];
		int[][] columns = new int[9][9];
		int[][] boxes = new int[9][9];

		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				char c = board[i][j];
				if (c != '.') {
					int num = c - '1';
					// 关注点，计算小宫格索引公式
					int boxIndex = (i / 3) * 3 + j / 3;
					// 行判断
					if (rows[i][num] == 1) {
						return false;
					} else {
						rows[i][num] = 1;
					}
					// 列判断
					if (columns[j][num] == 1) {
						return false;
					} else {
						columns[j][num] = 1;
					}
					// 小宫格判断
					if (boxes[boxIndex][num] == 1) {
						return false;
					} else {
						boxes[boxIndex][num] = 1;
					}
				}
			}
		}
		return true;
	}

	/**
	 * @author: ZhouJie
	 * @date: 2020年4月3日 下午9:30:03 
	 * @param: @param board
	 * @param: @return
	 * @return: boolean
	 * @Description: 3-进一步压缩空间，使bit位来计算数据
	 *
	 */
	public boolean isValidSudoku_3(char[][] board) {
		// 行列小宫格的编号
		int[] rows = new int[9];
		int[] columns = new int[9];
		int[] boxes = new int[9];

		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				char c = board[i][j];
				if (c != '.') {
					int num = c - '1';
					// 关注点，计算小宫格索引公式
					int boxIndex = (i / 3) * 3 + j / 3;
					// 行判断
					if (((rows[i] >> num) & 1) == 1) {
						return false;
					} else {
						rows[i] |= 1 << num;
					}
					// 列判断
					if (((columns[j] >> num) & 1) == 1) {
						return false;
					} else {
						columns[j] |= 1 << num;
					}
					// 小宫格判断
					if (((boxes[boxIndex] >> num) & 1) == 1) {
						return false;
					} else {
						boxes[boxIndex] |= 1 << num;
					}
				}
			}
		}
		return true;
	}
}

原文链接:https://www.cnblogs.com/izhoujie/p/12629853.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有