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
'.'.本题求一个sudoku是否是valid，一个valid的sudoku必须满足， 每一行每一列的数字都是1-9，并且没有重复的数字，每一个3*3的小九宫格也不能有重复的数字，这个题目中，只考虑数字重复的情况，而不去考虑数字是不是在1-9之间。
要判断数字在1-9之间是否重复，由于是连续的数字，可以直接用一个一维数组size为10,(1-9+'.')，思想和bitvector相同， index为当前数字，value为标记，如果当前数字在数组里面标记为1，那么说明该数字之前出现过，此时出现重复情况。 对于每一行每一列可以用一个二重循环来进行check，对于每一个九宫格，其实也可以用二重循环check,只是当前的坐标需要进行一下转换，即第i个九宫格里面的9个坐标怎么用i,j表示呢？
board[3 * (i/3)+(j/3)][3*(i%3)+j%3]
class Solution {
private:
bool check(int* arr, int val) {
if (val < 0) return true;
if (arr[val] == 1) return false;
arr[val] = 1;
return true;
}
public:
bool isValidSudoku(vector<vector<char>>& board) {
//sanity chck
if (board.size() == 0 || board[0].size() == 0) return false;
//use 3 int array to do the check
int col[10] = {0};
int row[10] = {0};
int small[10] = {0};
for (int i = 0; i < 9; i++) { //ith row
memset(col, 0, sizeof(col));
memset(row, 0, sizeof(row));
memset(small, 0, sizeof(small));
for (int j = 0; j < 9; j++) { //jth col
if (!check(col, board[j][i]-'0') || !check(row, board[i][j]-'0') ||!check(small, board[3 * (i/3)+(j/3)][3*(i%3)+j%3]-'0'))
return false;
}
}
return true;
}
};
Leetcode 37: sudoku solver
Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character
'.'.You may assume that there will be only one unique solution.
题目大意： 填 sudoku 9*9的格子， 每一行、列不能有重复的数字，并且3*3的格子也不能有重复的数字。
解题思路： 对于这种有一定规律地填格子的游戏，完全可以用DFS的思想来做， 因为每一个格子的填法都相同，每填完一个格子就对相应的行和列以及相应的3*3的格子进行检查，如果是valid，那么就对下一个格子进行填写。
M1： worst one！！！
先填列，再填行，如果一个格子不需要填， 跳过这个格子再填下一个。
这样填法，对于一些case，可能会出现超时，比如说，一个9*9的格子里面已经有很多已经填好的数字了，只有仅仅的几列都空格，这种情况跟worst case的时间复杂度是相同的。
M2： 如何避免这种case呢？？？
可以做一个preprocessing，把需要填的empty格子都记录下来，不用一个一个地去遍历original的每一个格子，只要直接对事先记录的empty的格子进行填写，如何判断填完了呢？ 可以利用一个计数器 cur, 表示目前已经填好的empty的格子。 每填完一个cur+1dfs到下一层，base case 是当cur == empty.size()的时候就可以return了，代表已经填好了。 这样做对于大多数的case可以节省很多时间。
class Solution {
private:
//check if the sudoku is valid
bool isValid(vector<vector<char>> &board, int i, int j) {
for (int k = 0; k < 9; k++) {
//check if there is a same num in ith row
if (k != j && board[i][k] == board[i][j]) {
return false;
}
//check if there is a same num in jth column
if (k != i && board[k][j] == board[i][j]) {
return false;
}
}
//check if there are dup nums in a 3*3 CELL
for (int m = i/3 * 3; m < i/3 * 3 + 3; m++) {
for (int n = j/3 *3; n < j/3 * 3 + 3; n++) {
if ((i != m || j != n) && (board[m][n] == board[i][j])) {
return false;
}
}
}
return true;
}
//fill the sudoku, fill column first then fill row
bool helper(vector<vector<char>> &board, vector<int> empty, int cur) {
//base case
if (cur == empty.size()) return true;
int index = empty[cur];
int row = index/9;
int col = index%9;
for (int k = 1; k <= 9; k++) {
board[row][col] = k + '0';
if (isValid(board, row, col)) {
if (helper(board,empty, cur+1)) {
return true;
}
}
board[row][col] = '.';
}
return false;
}
public:
void solveSudoku(vector<vector<char>>& board) {
//sanity check
if (board.size() == 0 || board.size() != 9 || board[0].size() != 9) return;
vector<int> empty;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == '.') {
empty.push_back(i * 9 + j);
}
}
}
helper(board, empty, 0);
}
};
class Solution {
private:
//check if the sudoku is valid
bool isValid(vector<vector<char>> &board, int i, int j) {
for (int k = 0; k < 9; k++) {
//check if there is a same num in ith row
if (k != j && board[i][k] == board[i][j]) {
return false;
}
//check if there is a same num in jth column
if (k != i && board[k][j] == board[i][j]) {
return false;
}
}
//check if there are dup nums in a 3*3 CELL
for (int m = i/3 * 3; m < i/3 * 3 + 3; m++) {
for (int n = j/3 *3; n < j/3 * 3 + 3; n++) {
if ((i != m || j != n) && (board[m][n] == board[i][j])) {
return false;
}
}
}
return true;
}
//fill the sudoku, fill column first then fill row
bool helper(vector<vector<char>> &board, vector<int> empty, int cur) {
//base case
if (cur == empty.size()) return true;
int index = empty[cur];
int row = index/9;
int col = index%9;
for (int k = 1; k <= 9; k++) {
board[row][col] = k + '0';
if (isValid(board, row, col)) {
if (helper(board,empty, cur+1)) {
return true;
}
}
board[row][col] = '.';
}
return false;
}
public:
void solveSudoku(vector<vector<char>>& board) {
//sanity check
if (board.size() == 0 || board.size() != 9 || board[0].size() != 9) return;
vector<int> empty;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == '.') {
empty.push_back(i * 9 + j);
}
}
}
helper(board, empty, 0);
}
};
Leetcode 51: N-Queen
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
题目大意： N皇后问题，使每行每列还有对角线上放置的皇后不会相互攻击。
解题思路： DFS， 对于DFS树，总共有N层，代表有这么多行，每一层一共是N种Q的放置方法，放置在该行的不同列上，但是这个是可以剪枝的DFS，因为并不是每种放置都是Valid的。 所以在每放一个Q时应该去检查这样是否valid,如果valid就DFS往下一层放置。
对于Valid函数，最直观的写法是，检测该列上是否有Q，检测左对角线是否有Q，检测右对角线是否有Q，但是这个函数的时间复杂度是O（n）。有没有能一次性判断是否valid的方法，使得时间复杂度是O（1）呢？？有！ 可以利用一个vector记录每一行上Q所在的列，然后遍历所有的层，如果vector上记录的该层Q所在列和此列正好相同就说明冲突，或者对角线x轴差距和y轴差距相同，则对角线冲突。 if(state[i] == col || abs(row - i) == abs(col - state[i]))。因为DFS里面判断valid的次数很多，优化VALID函数可以很大程度上优化运行效率。
class Solution {
private:
bool isValid(vector<int> state, int col, int row) {
for(int i = 0; i < row; i++)//只需要判断row前面的行，因为后面的行还没有放置
if(state[i] == col || abs(row - i) == abs(col - state[i]))
return false;
return true;
// return true;
}
void helper(int n, vector<string> solu, vector<vector<string>> &rst, int row, vector<int> state) {
//base case
if (row == n) {
rst.push_back(solu);
return;
}
for (int i = 0; i < n; i++) {
solu[row][i] = 'Q';
state[row] = i;
if (isValid(state, i, row))
helper(n, solu, rst, row+1,state);
solu[row][i] = '.';
state[row] = -1;
}
}
public:
//use dfs to solve
vector<vector<string> > solveNQueens(int n) {
string s = "";
vector<string> solu;
vector<vector<string>> rst;
vector<int> state(n, -1); //state to keep track of the position of Queen in each row
//sanity check
if(n == 0) return rst;
for (int i = 0; i < n; i++) {
s = "";
for (int j = 0; j < n; j++) {
s += '.';
}
solu.push_back(s);
}
// rst.push_back(solu);
helper(n, solu, rst,0, state);
return rst;
}
};
No comments:
Post a Comment