时间轴

2025-11-14

init

题目：

P36 有效的数独

https://leetcode.cn/problems/valid-sudoku/description/?envType=study-plan-v2&envId=top-interview-150


直接无脑比较就行
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <vector>
#include <unordered_set>

using std::vector;
using std::unordered_set;

#define BOARD_LENGTH 9
#define SMALL_BOARD_LENGTH 3
class Solution {
    public:
	bool judge(vector<vector<char> > &board, int start_i, int start_j, int sn)
	{
		unordered_set<char> uset;
		int i, j;
		for (i = start_i; i < start_i + sn; i++) {
			for (j = start_j; j < start_j + sn; j++) {
				if (board[i][j] == '.') {
					continue;
				}
				if (uset.count(board[i][j])) {
					return false;
				}
				uset.insert(board[i][j]);
			}
		}
		return true;
	}
	bool isValidSudoku(vector<vector<char> > &board)
	{
		// 9*9
		int i, j;
		int n = BOARD_LENGTH;
		int sn = SMALL_BOARD_LENGTH;
		// 每一行所有元素必须只出现一次

		for (i = 0; i < n; i++) {
			unordered_set<char> uset;
			for (j = 0; j < n; j++) {
				if (board[i][j] == '.') { //不统计空白格
					continue;
				}
				if (uset.count(board[i][j])) {
					return false;
				}
				uset.insert(board[i][j]);
			}
		}
		//每列所有元素只出现一次
		for (j = 0; j < n; j++) {
			unordered_set<char> uset;
			for (i = 0; i < n; i++) {
				if (board[i][j] == '.') {
					continue;
				}
				if (uset.count(board[i][j])) {
					return false;
				}
				uset.insert(board[i][j]);
			}
		}
		// 3* 3宫格只出现一次
		for (i = 0; i < n; i += sn) {
			for (j = 0; j < n; j += sn) {
				if (!judge(board, i, j, sn)) {
					return false;
				}
			}
		}
		return true;
	}
};