leetcode解题: Valid Sudoku (36)

发表于 | 分类于

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character ‘.’.

A partially filled sudoku which is valid.

Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

解法1： O（N N） Time + O(NN) Space, 一次遍历

本题要满足三个条件，行，列以及小方块都不能包含重复的数字。
可以用三个数组记录每一个条件是否满足，因为每个条件有9行，9列或者9个小方块。 每一个条件能出现的数字只有1到9。
那么每次扫描一个数字时，判断三个条件是否出现过一样的数字，如果有则返回false。
这样的做法好处是只需要遍历一次，代码很整洁。
要注意的是在计算小方块的index的时候， 用了k = i / 3 3 + j / 3, 注意这里因为i是int，所以不能把/33抵消掉。
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
       
       bool rule1[9][9] = {false}, rule2[9][9] = {false}, rule3[9][9] = {false};
       
       for (int i = 0; i < board.size(); ++i) {
           for (int j = 0; j < board[0].size(); ++j) {
               if (board[i][j] != '.') {
                   int digit = board[i][j] - '0' - 1;
                   int smallMatrixIndex = i / 3 * 3 + j / 3;
                   if (rule1[i][digit] || rule2[j][digit] || rule3[smallMatrixIndex][digit]) {
                       return false;
                   }
                   rule1[i][digit] = rule2[j][digit] = rule3[smallMatrixIndex][digit] = true;
               }
           }
       }
       
       return true;
    }
};

Java

1

解1法2： O（N * N） Time + O(1) Space， 三次遍历

C++

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
class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        
        unordered_map<int, int> map;
        // check row
        for (int i = 0; i < board.size(); ++i) {
            map.clear();
            for (int j = 0; j < board[i].size(); ++j) {
                if (board[i][j] == '.') {
                    continue;
                }
                if (map[board[i][j]] != 0) {
                    return false;
                }
                map[board[i][j]] = 1;
            }
        }
        
        // check col
        int row = board.size();
        int col = board[0].size();
        for (int i = 0; i < col; ++i) {
            map.clear();
            for (int j = 0; j < row; ++j) {
                if (board[j][i] == '.') {
                    continue;
                }
                if (map[board[j][i]] != 0) {
                    return false;
                }
                map[board[j][i]] = 1;
            }
        }
        
        // check small matrix
        for (int i = 0; i < row / 3; ++i) {
            for (int j = 0; j < col / 3; ++j) {
                map.clear();
                for (int k = i * 3; k < i * 3 + 3; ++k) {
                    for (int m = j * 3; m < j * 3 + 3; ++m) {
                        if (board[k][m] == '.') {
                            continue;
                        }
                        if (map[board[k][m]] != 0) {
                            return false;
                        }
                        map[board[k][m]] = 1;
                    }
                }
            }
        }
        
        return true;
        
    }
};

Java

1