# 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```这个数字

之后做bit and看结果是否为0，看```board[i][j]```之前是否出现在第```i```行或第```j```列或第```((i/3)*3+(j/3))```的box里面过
## Code
### 思路一

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
### 思路一

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;
}
}

### 思路二

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)

2. new 的用法
创建一维阵列时（如本题）

    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];

创建二维阵列时

    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));```才可以