怎样应对IT面试与笔试-(八)

怎样应对IT面试与笔试-(八)

Backtracking(回溯法) 51. N-Queens 经典的N皇后问题,将n个皇后放到n*n的棋盘上,使得两两皇后不能攻击(同一行、同一列、同一斜线上的皇后都会自动攻击) 我们需要返回所有的可行方法,Q表示皇后位置,.表示空位。 像题目中给出的例子: Input: 4 Output: [ ["....

Backtracking(回溯法)

51. N-Queens

经典的N皇后问题,将n个皇后放到n*n的棋盘上,使得两两皇后不能攻击(同一行、同一列、同一斜线上的皇后都会自动攻击)
我们需要返回所有的可行方法,Q表示皇后位置,.表示空位。
像题目中给出的例子:

Input: 4
Output: [
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

先给出代码:

class Solution {
public:
    vector> solveNQueens(int n) {
        vector > res;
        vector nQueens(n,string(n,'.'));
        solveNQueens(res,nQueens,0,n);
        return res;
    }
    void solveNQueens(vector >&res, vector& nQueens,int row,int &n)
    {
        if(row == n)
        {
            res.push_back(nQueens);
            return;
        }
        for(int col = 0; col != n; ++col)
        {
            //isValid是用来保证每一行、每一列和对角线都没有冲突的皇后
            if(isValid(nQueens,row,col,n))
            {
                nQueens[row][col] = 'Q';
                //递归,深度优先搜索
                solveNQueens(res,nQueens,row + 1, n);
                //清理现场
                nQueens[row][col] = '.';
            }
        }
    }
    bool isValid(vector &nQueens,int row,int col,int &n)
    {
        for(int i = 0; i != row; ++i)
        {
            if(nQueens[i][col] == 'Q')
                return false;
        }
        for(int i = row -1,j = col -1; i >=0 && j >=0;--i,--j)
        {
            if(nQueens[i][j] == 'Q')
                return false;
        }
        for(int i = row -1,j = col + 1; i >= 0 && j 

以2*2的简单棋盘说明:

51.png

(1)箭头上的数字表示了程序的执行流程
(2)红色箭头是进行深度优先探索过程
(3)黑色箭头是进行回溯(清理现场)过程

回溯作为一种算法思想,通常都是使用递归这种方式来实现

怎样应对IT面试与笔试-(一)
怎样应对IT面试与笔试-(二)
怎样应对IT面试与笔试-(三)
怎样应对IT面试与笔试-(四)
怎样应对IT面试与笔试-(五)
怎样应对IT面试与笔试-(五-1)
怎样应对IT面试与笔试-(六)
怎样应对IT面试与笔试-(七)
怎样应对IT面试与笔试-(八)
怎样应对IT面试与笔试-(九)
怎样应对IT面试与笔试-(十)
怎样应对IT面试与笔试-(十一)
怎样应对IT面试与笔试-(十二)
怎样应对IT面试与笔试-(十三)
怎样应对IT面试与笔试-(十四)
怎样应对IT面试与笔试-(十五)
怎样应对IT面试与笔试-(十六)

文章来源于互联网:怎样应对IT面试与笔试-(八)

0

评论0

鱼翔浅底,鹰击长空,驼走大漠
没有账号? 注册  忘记密码?