《每周一道算法题》（九）有效的数独
2019-12-10 本文已影响0人
路飞_Luck
一 题目
36. 有效的数独
判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
- 数字 1-9 在每一行只能出现一次。
- 数字 1-9 在每一列只能出现一次。
- 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
image.png
上图是一个部分填充的有效的数独。
数独部分空格内已填入了数字，空白格用 '.' 表示。
示例 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 形式的。
二 解题思路一
2.1 计算每个数字所在九宫格的位置
image.png
假设row是行号，col是列号，box_index是九宫格的位置，则
boxIndex = (row / 3) * 3 + col / 3;
比如低7列第2行
- 核心代码如下
/// 有效的数独
- (BOOL)isValidSudoku:(NSArray<NSArray *> *)board {
NSMutableArray<NSMutableArray *> *rows = [NSMutableArray array];
NSMutableArray<NSMutableArray *> *cols = [NSMutableArray array];
NSMutableArray<NSMutableArray *> *boxes = [NSMutableArray array];
// 赋值数据
for (int i = 0; i < 9; i++) {
[rows addObject:[NSMutableArray array]];
[cols addObject:[NSMutableArray array]];
[boxes addObject:[NSMutableArray array]];
}
for (int row = 0; row < 9; row++) {
for (int col = 0; col < 9; col++) {
NSString *num = board[row][col];
if ([num isEqualToString:@"."]) {
continue;
}
if ([rows[row] containsObject:num]) {
return false;
}
if ([cols[col] containsObject:num]) {
return false;
}
// 计算每个数字所在九宫格的位置
int boxIndex = (row / 3) * 3 + col / 3;
if ([boxes[boxIndex] containsObject:num]) {
return false;
}
// 表示未出现过,则添加进数组中
[rows[row] addObject:num];
[cols[col] addObject:num];
[boxes[boxIndex] addObject:num];
}
}
return true;
}
- 测试代码
- (void)viewDidLoad {
[super viewDidLoad];
// Do any additional setup after loading the view, typically from a nib.
NSArray<NSArray *> *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"]];
NSArray<NSArray *> *board1 = @[
@[@"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"]];
BOOL result = [self isValidSudoku:board];
BOOL result1 = [self isValidSudoku:board1];
NSLog(@"result = %d, result2 = %d",result,result1);
}
- 运行结果
2019-12-08 20:39:43.251030+0800 09_ValidSudoku[44098:1854283] result = 1, result2 = 0
三 解题思路二
数组使用bool类型值变量
/// 有效的数独
- (BOOL)isValidSudoku2:(NSArray<NSArray *> *)board {
NSMutableArray<NSMutableArray *> *rows = [NSMutableArray array];
NSMutableArray<NSMutableArray *> *cols = [NSMutableArray array];
NSMutableArray<NSMutableArray *> *boxes = [NSMutableArray array];
// 赋值数据 - bool类型数据
for (int i = 0; i < 9; i++) {
NSMutableArray<NSNumber *> *bools = [NSMutableArray array];
for (int j = 0; j < 9; j++) {
[bools addObject:@(0)];
}
[rows addObject:bools.mutableCopy];
[cols addObject:bools.mutableCopy];
[boxes addObject:bools.mutableCopy];
}
int temNum = 0;
for (int row = 0; row < 9; row++) {
for (int col = 0; col < 9; col++) {
NSString *num = board[row][col];
if ([num isEqualToString:@"."]) {
continue;
}
temNum = num.intValue - 1;
if ([rows[row][temNum] intValue]) { // 表示之前第row行,temNum列出现过num元素
return false;
}
if ([cols[col][temNum] intValue]) { // 表示之前第col行,temNum列出现过num元素
return false;
}
// 计算每个数字所在九宫格的位置
int boxIndex = (row / 3) * 3 + col / 3;
if ([boxes[boxIndex][temNum] intValue]) {
return false;
}
// 表示未出现过,在temNum位置置为1
rows[row][temNum] = @(1);
cols[col][temNum] = @(1);
boxes[boxIndex][temNum] = @(1);
}
}
return true;
}
- 运行结果
2019-12-08 22:31:52.520964+0800 09_ValidSudoku[46472:1972554] result = 1, result2 = 0
四 解题思路三
使用字节运算
image.png
举例如下
1.比如 row = 0, col = 0, num = 5，则将5所在位置1 << (num - 1)，即1左移4位处置为1.
9 8 7 6 5 4 3 2 1
0 0 0 0 1 0 0 0 0
2.比如 row = 0, col = 1, num = 3，则将3所在位置1 << (num - 1)，即1左移2位处置为1.
9 8 7 6 5 4 3 2 1
0 0 0 0 0 0 1 0 0
然后再将值进行累加，即 000010000 + 000000100
- 核心算法如下
/// 有效的数独
- (BOOL)isValidSudoku3:(NSArray<NSArray *> *)board {
NSMutableArray<NSNumber *> *rows = [NSMutableArray array];
NSMutableArray<NSNumber *> *cols = [NSMutableArray array];
NSMutableArray<NSNumber *> *boxes = [NSMutableArray array];
// 赋值数据
for (int i = 0; i < 9; i++) {
[rows addObject:@(0)];
[cols addObject:@(0)];
[boxes addObject:@(0)];
}
/** 解释说明 第一行第一列为5的时候
9 8 7 6 5 4 3 2 1
0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 &
-------------------
0 0 0 0 0 0 0 0 0 如果为零,表示5之前没有出现过,否则出现过
*/
int temNum = 0;
for (int row = 0; row < 9; row++) {
for (int col = 0; col < 9; col++) {
NSString *num = board[row][col];
if ([num isEqualToString:@"."]) {
continue;
}
temNum = 1 << (num.intValue - 1); // 比如5,则1左移4位
if ((rows[row].intValue & temNum) != 0) {
return false;
}
if ((cols[col].intValue & temNum) != 0) {
return false;
}
// 计算每个数字所在九宫格的位置
int boxIndex = (row / 3) * 3 + col / 3;
if ((boxes[boxIndex].intValue & temNum) != 0) {
return false;
}
// 表示未出现过,在temNum位置置为1
// 比如 row = 0,col = 0, num = 5,则在第5个位置为1,即1左移4位, 0 0 0 0 1 0 0 0 0
rows[row] = @(rows[row].intValue + (1 << (num.intValue - 1)));
cols[col] = @(cols[col].intValue + (1 << (num.intValue - 1)));
boxes[boxIndex] = @(boxes[boxIndex].intValue + (1 << (num.intValue - 1)));
}
}
return true;
}
- 运行结果如下
2019-12-10 22:47:37.233659+0800 09_ValidSudoku[51403:2236090] result = 1, result2 = 0
到此为止，每周一道算法题就告一段落了，喜欢我的文章可以阅读我的其他文章。
本文参考MJ老师的每周一道算法题
