《每周一道算法题》（九）有效的数独

作者: 路飞_Luck | 来源:发表于2019-12-10 23:04 被阅读0次

《每周一道算法题》（九）有效的数独
每天一题LeetCode【第27天】
leecode刷题（9）-- 有效的数独
ARTS第三周(2018-12-16)
每周一道算法题(九)
36、有效的数独 | 算法（leetode，附思维导图 + 全部
36.有效的数独
ARTS(09)
ARTS(05)
ARTS(07)

一题目

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老师的每周一道算法题

项目链接地址- 09_ValidSudoku

每周一道算法题 - 笔记

《每周一道算法题》（九）有效的数独
一题目 36. 有效的数独判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可...
每天一题LeetCode【第27天】
T36. Valid Sudoku【Medium】题目这是一道数独题，如何确定数独有效，参考数独规则数独板...
leecode刷题（9）-- 有效的数独
leecode刷题（9）-- 有效的数独有效的数独描述：判断一个 9x9 的数独是否有效。只需要根据以下规则...
ARTS第三周(2018-12-16)
1.Algorithm：每周至少做一个 leetcode 的算法题第一道算法题：https://leetcode...
每周一道算法题(九)
今天的算法题难度级别'Easy',不得不说'easy'就是比'medium'简单啊，哈哈。。。上周做的题目是in...
36、有效的数独 | 算法（leetode，附思维导图 + 全部
零标题：算法（leetode，附思维导图 + 全部解法）300题之（36）有效的数独前言 1）码农三少，一个...
36.有效的数独
LeetCode 的算法题 PHP解法记录判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数...
ARTS(09)
什么是 ARTS？算法(Algorithm): 每周至少一道 LeetCode 算法题，加强编程训练和算法学习 ...
ARTS(05)
什么是 ARTS？算法(Algorithm): 每周至少一道 LeetCode 算法题，加强编程训练和算法学习 ...
ARTS(07)
什么是 ARTS？算法(Algorithm): 每周至少一道 LeetCode 算法题，加强编程训练和算法学习 ...

《每周一道算法题》（九）有效的数独

一题目

36. 有效的数独

二解题思路一

2.1 计算每个数字所在九宫格的位置

三解题思路二

四解题思路三

相关文章

《每周一道算法题》（九）有效的数独

每天一题LeetCode【第27天】

leecode刷题（9）-- 有效的数独

ARTS第三周(2018-12-16)

每周一道算法题(九)

36、有效的数独 | 算法（leetode，附思维导图 + 全部

36.有效的数独

ARTS(09)

ARTS(05)

ARTS(07)

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

《每周一道算法题》（九）有效的数独

一 题目

二 解题思路一

2.1 计算每个数字所在九宫格的位置

三 解题思路二

四 解题思路三

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

一题目

二解题思路一

三解题思路二

四解题思路三