数据结构003:有效的数独
原文链接:数据结构003:有效的数独
题目
请你判断一个
9 x 9
的数独是否有效。只需要 根据以下规则 ,验证已经填入的数字是否有效即可。数字
1-9
在每一行只能出现一次。 数字1-9
在每一列只能出现一次。 数字1-9
在每一个以粗实线分隔的3x3
宫内只能出现一次。(请参考示例图)注意:
一个有效的数独(部分已被填充)不一定是可解的。 只需要根据以上规则,验证已经填入的数字是否有效即可。 空白格用
'.'
表示。示例 1:
数独.png 输入:board = [["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:
输入:board = [["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 存在, 因此这个数独是无效的。
题解
根据题目的规则,数独需要满足三个规则,针对规则一和二可知,我们在遍历每个元素的时候,需要判断该元素所在行和列中是否出现过,即可判断该元素是否满足规则一和二,因此我们可以针对每一行、每一列出现元素的次数作为校验标准,例如声明两个二维数组row[9][9] 和col[9][9] 分别代表行和列上面0-9 出现的次数。例如row[1][2] 表示第1行中,出现2的次数,col[4][3] 表示第4列出现3的次数(都是从第0行/列开始算的)。对于数独数组第i 行j 列上的数值n=board[i][j] ,首先将row[i][n] 上对应的值加一,再将col[j][n] 也加一,然后判断row[i][n] 和row[i][n] 的值是否大于1,大于1则表明i 行或者j 列数字n 出现的次数大于1,即不唯一。不满足规则一或者二。
对于规则三,我们可以根据元素board[i][j] 的i 和j 的索引除以3来进行判断其属于哪个小九宫格,即其对应的小九宫格的索引为i/3 和j/3 。因此我们可构建一个box[3][3][9] 的三位数组来记录每个小九宫格中0-9 出现的次数,例如box[1][2][3] 表示第一行第二列的九宫格中出现数字3的次数,我们的思路与row 和col 一样,遍历每个元素n=board[i][j] ,并将box[i/3][j/3][n] 的值加一,在判断其是否大于1。
通过上面的分析,我们的实现代码如下:
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
int row[9][9] = {0};
int col[9][9] = {0};
int box[3][3][9] = {0};
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
char c = board[i][j];
if (c == '.') continue;
int n = c - '1';
row[i][n]++;
col[j][n]++;
box[i / 3][j / 3][n]++;
if (row[i][n] > 1 || col[j][n] > 1 || box[i / 3][j / 3][n] > 1) {
return false;
}
}
}
return true;
}
};
由于数独共有81个单元格,只需要对每个单元格遍历一次即可,因此其时间复杂度为O(1) 。由于数独的大小固定,因此空间的大小也是固定的,空间复杂度也为O(1) 。
相关文章
- 客观评价华为的OS鸿蒙系统
- 【Docker Desktop】在 Windows 上安装 Docker Desktop
- 【clearos】安装clearos系统
- 力扣刷题记(罗马数字转整数)。。sizeof和s.length()的区别
- 论class和struct的区别
- 如何监测车间有毒有害气体?
- “预测”比“解释”重要的多
- YAML快速入门
- 【FusionCompute】介绍(一)
- 从卖场陈列规划到业绩指标
- 这份巨详细的足球比赛数据值得拥有(有世界杯,有梅西)
- Rasa 基于规则的对话管理: 天气预报机器人
- 【FusionCompute】使用VMware Workstaion安装部署CNA(二)
- 如何在XMLMap端口修改字段映射?
- 从JAVA内存到垃圾回收,带你深入理解JVM
- 透过现象看本质:Java类动态加载和热替换
- logstash处理多行日志-处理java堆栈日志
- Java High Level REST Client 使用地理位置查询
- 垃圾回收你懂,Java垃圾回收你懂吗?
- 几款Java开发者必备常用的工具,准点下班不在话下