LeetCode36. Valid Sudoku

描述

判断该数独是否有效

解决

---

我想的是分别遍历行列与9个方块

class Solution { public: bool isValidSudoku(vector<vector<char>>& board) { uint8_t a[10] = {0}; uint8_t b[10] = {0}; for (int i = 0; i < 9; ++i) { for (int j = 0; j < 9; ++j) { if (board[i][j] != '.') { if((++a[board[i][j] - '0']) > 1) return false; } if (board[j][i] != '.') { if ((++b[board[j][i] - '0']) > 1) return false; } } memset(b, 0, sizeof(b)), memset(a, 0, sizeof(a)); } uint8_t arr[10] = {0}; for (int i = 0; i < 3; ++i) { for (int j = 0; j < 3; ++j) { // cout << "j" << j << endl; for (int pos_x = i * 3; pos_x < i * 3 + 3; ++pos_x) { for (int pos_y = j * 3; pos_y < j * 3 + 3; ++pos_y) { // cout << "why " << pos_y << endl; if (board[pos_x][pos_y] != '.') { if ((++arr[board[pos_x][pos_y] - '0']) > 1) // { // cout << "3= " << pos_x << ' ' << pos_y << endl; return false; // } } } } memset(arr, 0, sizeof(arr)); } } return true; } };

---

别人的算法，O(n^2)的遍历，算法链接

class Solution { public: bool isValidSudoku(vector<vector<char>>& board) { uint8_t row_arr[10][10] = {0}; uint8_t col_arr[10][10] = {0}; uint8_t z_arr[10][10] = {0}; for (int i = 0; i < 9; ++i) { for (int j = 0; j < 9; ++j) { if (board[i][j] != '.') { int temp = board[i][j] - '0'; if ((row_arr[i + 1][temp]++) || (col_arr[j + 1][temp]++) || (z_arr[i / 3 * 3 + j / 3][temp]++)) return false; } } } return true; } };