LeetCode 36. 有效的数独

本文介绍: 请你判断一个 9 x 9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3×3 宫内只能出现一次。

有效的数独

请你判断一个 9 x 9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3×3 宫内只能出现一次。

一次遍历法

有效数独的三个条件：
1.同一个数字在每一行只能出现一次；
2.同一个数字在每一列只能出现一次；
3.同一个数字在每一个小九宫格只能出现一次。

去重类问题，我们想到了哈希表的使用，如何结合起来呢？
我们首先考虑行数据，每行有个哈希表，记录了该行中数字出现的频率，数据可组织为：rows = [[key:val]],
由于数独中的数字范围是1到9，因此可以使用数组代替哈希表进行计数,数据可组织为：rows = [[Int]]，减少复杂度。
同理，列数据可得

那么小九宫有何规律呢？
仔细观察发现，9×9 分块后变成了3×3，那么小九宫格的索引自然就是 i/3, j/3，此处记录数据的数组容量仍然为9
数据用三维数组形式表示为：subboxes = [[[Int]]]

复杂度分析
时间复杂度：O(1)，注意，由于遍历了9×9 = 81次，常量级别的，因此时间复杂度为O(1)
空间复杂度：O(1)，占用了常量空间用来记录变量

Swift

func isValidSudoku(_ board: [[Character]]) -> Bool {
    
        var rows:[[Int]] = Array(repeating: Array(repeating: 0, count: 9), count: 9)
        var columns = Array(repeating: Array(repeating: 0, count: 9), count: 9)
        var subboxes = Array(repeating: Array(repeating: Array(repeating: 0, count: 9), count: 3), count: 3)
        
        for i in 0..<9 {
            for j in 0..<9 {
                let c = board[i][j]
                
                if c != "." {
                    let index:Int = c.wholeNumberValue! - 1
                    
                    rows[i][index] += 1
                    columns[j][index] += 1
                    subboxes[i/3][j/3][index] += 1;
                    
                    if rows[i][index] > 1 || columns[j][index] > 1 || subboxes[i/3][j/3][index] > 1 {
                        return false
                    }
                }
            }
        }
        
        return true
    }

OC

- (BOOL)isValidSudoku:(NSArray *)board {
    NSMutableArray *rows = [NSMutableArray arrayWithCapacity:9];
    for (NSInteger i=0; i<9; i++) {
        
        NSMutableArray *itemArr = [NSMutableArray array];
        for (NSInteger j=0; j<9; j++) {
            [itemArr addObject:@(0)];
        }
        [rows addObject:itemArr];
    }
    
    NSMutableArray *columns = [NSMutableArray arrayWithCapacity:9];
    for (NSInteger i=0; i<9; i++) {
        NSMutableArray *itemArr = [NSMutableArray array];
        for (NSInteger j=0; j<9; j++) {
            [itemArr addObject:@(0)];
        }
        [columns addObject:itemArr];
    }
    
    NSMutableArray *subbox = [NSMutableArray arrayWithCapacity:3];
    for (NSInteger i=0; i<3; i++) {
        NSMutableArray *itemArr = [NSMutableArray array];
        for (NSInteger j=0; j<3; j++) {
            NSMutableArray *subItemArr = [NSMutableArray array];
            for (NSInteger k=0; k<9; k++) {
                [subItemArr addObject:@(0)];
            }
            [itemArr addObject:subItemArr];
        }
        [subbox addObject:itemArr];
    }
    
    for (NSInteger i=0; i<9; i++) {
        for (NSInteger j=0; j<9; j++) {
            NSString *c = board[i][j];
            
            if (![c isEqualToString:@"."]) {
                NSInteger idx = [c integerValue];
                
                rows[i][idx] = @([rows[i][idx] integerValue] + 1);
                columns[j][idx] = @([columns[j][idx] integerValue] + 1);
                subbox[i/3][j/3][idx] = @([subbox[i/3][j/3][idx] integerValue] + 1);
                
                if ([rows[i][idx] integerValue] > 1 || [columns[j][idx] integerValue] > 1 ||
                    [subbox[i/3][j/3][idx] integerValue] > 1) {
                    return NO;
                }
            }
        }
    }
    
    return YES;
}