leetcode题解日练--2016.09.06

本文主要是介绍leetcode题解日练--2016.09.06，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

不给自己任何借口

今日题目：

1、数独的解

2、N-皇后II

3、N-皇后

今日摘录：

大抵浮生若梦，姑且此处销魂。
——曾国藩

37. Sudoku Solver | Difficulty: Hard

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.

A sudoku puzzle…

…and its solution numbers marked in red.

tag：回溯|哈希表
题意：数独的解

思路：
1、dfs+回溯

class Solution {
public:void solveSudoku(vector<vector<char>>& board){solve(board);}bool solve(vector<vector<char>>& board) {for(int r = 0;r<9;r++){for(int c=0;c<9;c++){if(board[r][c]=='.'){for (char k = '1'; k <= '9'; k++){if(isvalid(board,r,c,k)){board[r][c] = k;if(solve(board))    return true;board[r][c] = '.';}}return false;}}}return true;}bool isvalid(vector<vector<char>>& board,int row,int col,char k){for(int i=0;i<9  ;i++)if(board[i][col]==k)    return false;for(int i=0;i<9 ;i++)if(board[row][i]==k)    return false;for(int i=(row/3)*3;i<(row/3+1)*3 ;i++){for(int j=(col/3)*3;j<(col/3+1)*3;j++){if(board[i][j]==k)    return false;}}return true;}
};

结果：53ms

52. N-Queens II | Difficulty: Hard

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

tag：回溯

题意：找到N皇后有多少个解
思路：
1、经典的回溯思想，边放置边剪枝。

class Solution {
public:
int totalNQueens(int n) {int res = 0;//cols代表因为列不冲突的情况，main是主对角线，anti是辅对角线。为何对角线的标志位数组要比cols大呢？vector<bool> cols(n,true);vector<bool> main(2*n-1,true);vector<bool> anti(2*n-1,true);dfs(0,res,cols,main,anti);return res;
}
void dfs(int row,int&res,vector<bool> &cols,vector<bool> &main,vector<bool> &anti)
{if(row==cols.size()){res++;return ;}for(int col = 0;col<cols.size();col++){if(cols[col] && main[row-col+cols.size()-1]&&anti[row+col]){cols[col] = main[row-col+cols.size()-1]=anti[row+col] = false;dfs(row+1,res,cols,main,anti);cols[col] = main[row-col+cols.size()-1]=anti[row+col] = true;}}return;
}
};

结果：13ms

2、
使用位运算的方法：
row用一个Nbit位的数代表哪些位置是接下来还能放的，哪些位置是不能放的。
main：主对角线，代表主对角线对下一行选取位置的影响
anti：副对角线，代表副对角线对下一行选取位置的影响

class Solution {
public:void queenBit(int row,int main,int anti,const int all_queen)
{if(row!=all_queen){int pos = all_queen & ~(row|main|anti);while(pos!=0){int p = pos&-pos;pos-=p;queenBit(row+p,(main+p)<<1,(anti+p)>>1,all_queen);}}else{res++;return ;}
}int totalNQueens(int n) {res = 0;int all_queen = (1<<n)-1;queenBit(0,0,0,all_queen);return res;
}
private:int res;};

结果：0ms

51. N-Queens | Difficulty: Hard

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the 4-queens puzzle:

[
[“.Q..”, // Solution 1
“…Q”,
“Q…”,
“..Q.”],

[“..Q.”, // Solution 2
“Q…”,
“…Q”,
“.Q..”]
]
tag：回溯

题意：找到N皇后的每个解是什么。
思路：
1、经典的回溯思想，边放置边剪枝。

class Solution {
public:void dfs(int row,vector<vector<string>>&res,vector<string>path,vector<bool> &cols,vector<bool> &main,vector<bool> &anti,const string str){if(row==cols.size()){res.push_back(path);return ;}for(int col = 0;col<cols.size();col++){if(cols[col] && main[row+col]&&anti[row-col+cols.size()-1]){string tmp = str;tmp[col] = 'Q';path.push_back(tmp);cols[col] = main[row+col]=anti[row-col+cols.size()-1] = false;dfs(row+1,res,path,cols,main,anti,str);path.pop_back();tmp[col] = '.';cols[col] = main[row+col]=anti[row-col+cols.size()-1] = true;}}return;}vector<vector<string>> solveNQueens(int n) {vector<bool> cols(n,true);vector<bool> main(2*n-1,true);vector<bool> anti(2*n-1,true);vector<string> path;string str = dot.substr(0,n);dfs(0,res,path,cols,main,anti,str);return res;}
private:vector<vector<string>>res;string dot = "......................";};

结果：29ms

class Solution {
public:void queenBit(int row,int main,int anti,const int all_queen,const string str,vector<string>&path){if(row!=all_queen){int pos = all_queen & ~(row|main|anti);while(pos!=0){int p = pos&-pos;pos-=p;string tmp = str;int i = log10(p)/log10(2);tmp[i] = 'Q';path.push_back(tmp);queenBit(row+p,(main+p)<<1,(anti+p)>>1,all_queen,str,path);path.pop_back();tmp[i] = '.';}}else{res.push_back(path);return ;}}vector<vector<string>> solveNQueens(int n) {int all_queen = (1<<n)-1;string str = dot.substr(0,n);vector<string> path;queenBit(0,0,0,all_queen,str,path);return res;}
private:vector<vector<string>>res;string dot = "......................";
};