最近就在网上闲逛时，我撞见了一个很有意思的话题：「用一件事证明你已经开始消费降级了！」又到了网友们最擅长的领域了，我不打开留言都知道，留言肯定是百家争鸣。

果不其然，上来就非常炸裂，有位网友说：「别人怀孕7个月的二手女友都打算接盘了。」这话虽然是开玩笑的，但不得不说，还是非常炸裂。

然后是正常的回答，「我现在都不怎么出门了。」这确实是符合题意。

还有人说，「以前还敢去K个歌，现在都是大桥边合唱」咱就是说，这歌你是非唱不可吗？

当然，大佬虽迟但到，「卫生纸洗洗还能用」。为了省钱，你也是真拼啊。

留言里，甚至还有我都不敢放出来的回答，网友的才华我是佩服了。看到这些回答，说明大家状态还是非常不错的。不管是在开玩笑，还是真的苦中作乐，良好的心态必不可少。

也许我们的消费真的降级了。从大手大脚，到现在能省就省，但我们对生活的态度从未降级，依旧乐观。

下面是今日的大厂算法题

今日算法题 ，来自LeetCod e的第36题：有效的数独，下面是我 的算 法思路及实现，让我们来看看吧。

# 算法题目

判断一个 9x9 的数独是否有效。仅需要根据以下规则，验证已经填入的数字是否有效即可。

1. 数字 1-9 在每一行只能出现一次。

   
   

2. 数字 1-9 在每一列只能出现一次。

3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

数独部分空格内已填入了数字，空白格用 '.' 表示。

注意：

# 算法思路

本问题可以通过使用哈希表来高效解决。具体步骤如下：

1. 创建三个类型为哈希表的数据结构，分别用于存储每一行、每一列以及每一个小 3x3 宫格中数字出现的情况。

2. 遍历数独：

# 代码实现

Java实现

public boolean isValidSudoku(char[][] board) { HashSet<String> seen = new HashSet<>();for (int i = 0; i < 9; i++) {for (int j = 0; j < 9; j++) {char number = board[i][j];if (number != '.') {if (!seen.add(number + " in row " + i) || !seen.add(number + " in column " + j) || !seen.add(number + " in block " + i / 3 + "-" + j / 3)) {returnfalse; } } } }returntrue;}

JavaScript实现

functionisValidSudoku(board) {let rows = newArray(9).fill(0).map(() =>newSet());let cols = newArray(9).fill(0).map(() =>newSet());let boxes = newArray(9).fill(0).map(() =>newSet());for (let i = 0; i < 9; i++) {for (let j = 0; j < 9; j++) {let num = board[i][j];if (num !== '.') {let boxIndex = Math.floor(i / 3) * 3 + Math.floor(j / 3);if (rows[i].has(num) || cols[j].has(num) || boxes[boxIndex].has(num)) {returnfalse; } rows[i].add(num); cols[j].add(num); boxes[boxIndex].add(num); } } }returntrue;}

Go实现

funcisValidSudoku(board [][]byte)bool {var rows, cols [9][9]intvar boxes [3][3][9]intfor i := 0; i < 9; i++ {for j := 0; j < 9; j++ {if board[i][j] != '.' { num := board[i][j] - '1'if rows[i][num] == 1 || cols[j][num] == 1 || boxes[i/3][j/3][num] == 1 {returnfalse } rows[i][num], cols[j][num], boxes[i/3][j/3][num] = 1, 1, 1 } } }returntrue}

# 算法解析

通过使用哈希表来记录每个数字在行、列以及宫格中的出现情况，可以有效地检查数独是否满足给定的规则。

这种方法的时间复杂度为 O(1)，因为数独的大小是固定的（9x9），并且空间复杂度也是 O(1)，对于每个数字，我们只需要检查其是否已经在相应的行、列或宫格中出现过即可。

# 示例和测试

考虑以下数独：

53 . | . 7 . | . . .6 . . | 1 9 5 | . . .. 98| . . . | . 6 .------+------+------8 . . | . 6 . | . . 34 . . | 8 . 3 | . . 17 . . | . 2 . | . . 6------+------+------. 6 . | . . . |28 .. . . | 4 1 9 | . . 5. . . | . 8 . | . 79

通过上述任一实现的函数检查，这个数独是有效的，因为它满足所有给定的规则。

# 总结

有效的数独问题通过对数组和哈希表的灵活使用，提供了一种高效检查数独规则的方法。这种方法不仅适用于数独问题，还可以被应用到其他需要进行复杂规则验证的场景中。掌握这种算法思想，能够在解决类似问题时提高效率和准确性。

热门推荐