当前位置：首页 > news >正文

LeetCode 36. 有效的数独

news 来源：原创 2024/7/4 22:33:23

有效的数独

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

一次遍历法

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

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

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

复杂度分析
时间复杂度：O(1)，注意，由于遍历了9x9 = 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! - 1rows[i][index] += 1columns[j][index] += 1subboxes[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;
}