51
这道题算是回溯里面的难题。这个图能更好地理解回溯。
由上图可以将思路定为：采用回溯，用列控制每一个行中Q放的位置，如果当前Q放的位置合乎要求，那么就放置并递归，最后如果遍历到行数等于n了，就可以收集结果。判断合乎要求可以单独采用一个函数，这个函数需要验证当前位置的同一列（每行只有一个元素，不用检查行）、对角满足要求即可。
class Solution {
public:
vector<vector<string>> ans;
void backtrack(int n,int row,vector<string> &path)
{
if(row==n)
{
ans.push_back(path);
return ;
}
for(int col=0;col<n;col++)
{
if(check(n,row,col,path))
{
path[row][col]='Q';
backtrack(n,row+1,path);
path[row][col]='.';
}
}
}
bool check(int n,int row,int col,vector<string>& path)
{
for(int i=0;i<row;i++)
{
if(path[i][col]=='Q')
{
return false;
}
}
for(int i=row-1,j=col-1;i>=0 && j>=0 ; i--,j--)
{
if(path[i][j]=='Q')
{
return false;
}
}
for(int i=row-1,j=col+1;i>=0 && j<n;i--,j++)
{
if(path[i][j]=='Q')
{
return false;
}
}
return true;
}
vector<vector<string>> solveNQueens(int n) {
std::vector<std::string> path(n, std::string(n, '.'));
backtrack(n,0,path);
return ans;
}
};
35
这道题就是二分法的简单应用，本题多了一种情况:没查到就要返回插入的下标，这个直接在结尾返回左边的指针就行。
74
这道题也是二分法，可以先比较头尾元素，找到target所在行，再在行里面用二分法查找。
