---
# System prepended metadata

title: 0036. Valid Sudoku
tags: [Leetcode, HashMap, Medium]

---

#  0036. Valid Sudoku
###### tags: `Leetcode` `Medium` `HashMap`
Link: https://leetcode.com/problems/valid-sudoku/
## 思路
### 思路一
遍历一次，用27个（column9个，row9个，box9个）分别记录每行每列每个3*3的格子里面，出现每个数字的频率，如果有遇到出现两次的，直接返回false

**什么时候用map，什么时候用unordered_map**
https://blog.csdn.net/batuwuhanpei/article/details/50727227
### 思路二
只用一个阵列存
每个元素都有27位
对于第```i```个元素
从右到左前9位中的第```j```位 代表第```i```行是否有```j+1```这个数字
从右到左第9~17位中的第```j```位 代表第```i```列是否有```j+1```这个数字
从右到左第18~26位中的第```j```位 代表第```i```个box是否有```j+1```这个数字

```mux,mux1,mux2```分别存拿到```board[i][j]```之后，做bit shift，将这个值label在一个默认位0的27位int数字当中的结果，mux是在第1位到第9位里面mark，mux2是在第9位到第17位里面mark，mux3是在18~26位里面mark

之后做bit and看结果是否为0，看```board[i][j]```之前是否出现在第```i```行或第```j```列或第```((i/3)*3+(j/3))```的box里面过
## Code
### 思路一
```c=
class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        unordered_map<int,int>* rows = new unordered_map<int,int> [9];
        unordered_map<int,int>* columns = new unordered_map<int,int> [9];
        unordered_map<int,int>* boxes = new unordered_map<int,int> [9];
        for(int i = 0;i < 9;i++){
            for(int j = 0;j < 9;j++){
                if(board[i][j] != '.'){
                    int num = board[i][j] - '0';
                    int box_index = (i/3)*3+j/3;
                    if(rows[i].find(num) == rows[i].end()){
                        rows[i].insert(make_pair<int,int>((int)num, 1));
                    }
                    else{
                        return false;
                    }
                    if(columns[j].find(num)==columns[j].end()){
                        columns[j].insert(make_pair<int,int>((int)num, 1));
                    }
                    else{
                        return false;
                    }
                    if(boxes[box_index].find(num)==boxes[box_index].end()){
                        boxes[box_index].insert(make_pair<int,int>((int)num, 1));
                    }
                    else{
                        return false;
                    }
                }
            }
        }
        return true;
    }
};
```
## Java Code
### 思路一
```java=
class Solution {
    public boolean isValidSudoku(char[][] board) {
        int[][] row = new int[9][9];
        int[][] col = new int[9][9];
        int[][] box = new int[9][9];
        for(int i = 0;i < 9;i++){
           for(int j = 0;j < 9;j++){
                if(board[i][j] == '.'){
                    continue;
                }
                int box_index = (i/3)*3+j/3;
                int val = board[i][j]-'1';
                if(row[i][val]==0 && col[j][val]==0 && box[box_index][val]==0){
                      row[i][val] = 1;
                      col[j][val] = 1;
                      box[box_index][val] = 1;
                }
                else{
                      return false;
                }
            }
        }
        return true;
    }
}
```
### 思路二
```java=
class Solution {
    public boolean isValidSudoku(char[][] board) {
        int[] arrayList = new int[9];
        int mux, mux2, mux3, box_index;
        for(int i = 0;i < 9;i++){
            for(int j = 0;j < 9;j++){
                if(board[i][j] == '.'){
                    continue;
                }
                mux = 1<<board[i][j]-'1';
                mux2 = 1<<(9+board[i][j]-'1');
                mux3 = 1<<(9+9+board[i][j]-'1');
                box_index = (i/3)*3+j/3;
                if((arrayList[i]&mux)==0 && (arrayList[j]&mux2)==0 && (arrayList[box_index]&mux3)==0){
                    arrayList[i] = arrayList[i]|mux;
                    arrayList[j] = arrayList[j]|mux2;
                    arrayList[box_index] = arrayList[box_index]|mux3;
                }
                else{
                    return false;
                }
            }
        }
        return true;
    }
}
```
## Result
###  思路一 in C++
Runtime: 16 ms, faster than **90.96%** of C++ online submissions for Valid Sudoku.
Memory Usage: 21.3 MB, less than **11.10%** of C++ online submissions for Valid Sudoku.
### 思路一 in Java
Your runtime beats **100.00 %** of java submissions.
Your memory usage beats **90.89 %** of java submissions.
### 思路二 in Java
Your runtime beats **100.00 %** of java submissions.
Your memory usage beats **98.01 %** of java submissions.
## Error
这一题遇到的小bug特别多，要注意的写法也很多
1. character转数字 ('0'->0 '1'->1)
    ```int num = board[i][j] - '0';```
2. new 的用法
    创建一维阵列时（如本题）
    ```c=
    unordered_map<int,int>* rows = new unordered_map<int,int> [9];
    unordered_map<int,int>* columns = new unordered_map<int,int> [9];
    unordered_map<int,int>* boxes = new unordered_map<int,int> [9];
    ```
    创建二维阵列时
    ```c=
    int **matrix = new int*[ROW];
    for(int i = 0; i < ROW; ++i) {
        matrix[i] = new int[COL];
    }
    ```
    注意是用[]，不是（）
3. 在insert的部分，原本我是这样写的```rows[i].insert(make_pair<int,int>(num, 1));```,但是出现了**no matching function for call to 'make_pair'** 这个error，后来改成```rows[i].insert(make_pair<int,int>((int)num, 1));```才可以