leetcode 51. N-Queens 、52. N-Queens II

51. N-Queens

使用isValid判断当前的位置是否合法

每次遍历一行，使用queenCol记录之前行的存储位置，一方面是用于判断合法，另一方面可以根据存储结果输出最终的结果

棋盘的斜线都是45°的，所以两个位置x的差值和y的差值应该是相等的

class Solution {

public:

    vector<vector<string> > solveNQueens(int n) {

        vector<vector<string> > result;

        if(n <= )

            return result;

        vector<int> queenCol(n,-);

        int curRow = ;

        solveNQueens(curRow,result,queenCol,n);

        return result;

    }

    void solveNQueens(int curRow,vector<vector<string> >& result,vector<int>& queenCol,int n){

        if(curRow == n){

            vector<string> res(n,string(n,'.'));

            for(int i = ;i < n;i++)

                res[i][queenCol[i]] = 'Q';

            result.push_back(res);

            return;

        }

        for(int i = ;i < n;i++){

            if(isValid(queenCol,curRow,i)){

                queenCol[curRow] = i;

                solveNQueens(curRow + ,result,queenCol,n);

                queenCol[curRow] = -;

            }

        }

    }

    bool isValid(vector<int> queenCol,int row,int col){

        for(int i = ;i < row;i++){

            if(queenCol[i] == col || abs(row - i) == abs(col - queenCol[i]))

                return false;

        }

        return true;

    }

};

52. N-Queens II

这个题更像是51题的简化版，51题需要把所有的可能性输出出来，这个题只需要输出不同的个数。代码基本和51题差不多，依旧使用dfs遍历就好。

注意：result加了引用! curRow没加引用！

result最终要作为返回值获得结果，所有的搜索情况都公用这个result，但是curRow，不同的搜索，搜索的值应该不一样

class Solution {

public:

    int totalNQueens(int n) {

        if(n <= )

            return ;

        vector<int> queenCol(n,-);

        int result = ;

        int curRow = ;

        totalNQueens(n,queenCol,result,curRow);

        return result;

    }

    void totalNQueens(int n,vector<int>& queenCol,int& result,int curRow){

        if(curRow == n){

            result++;

            return;

        }

        for(int i = ;i < n;i++){

            if(isValid(queenCol,curRow,i)){

                queenCol[curRow] = i;

                totalNQueens(n,queenCol,result,curRow+);

                queenCol[curRow] = -;

            }

        }

    }

    bool isValid(vector<int>& queenCol,int row,int col){

        for(int i = ;i < row;i++){

            if(queenCol[i] == col || abs(row - i) == abs(col - queenCol[i]))

                return false;

        }

        return true;

    }

};

另一种写法：

这种写法也是正确的，将queenCol的引用去掉，然后将queenCol[curRow] = -1;删掉，因为实际上不会回调回来。

如果你想用回调回来的，就必须queenCol[curRow] = -1

如果不用回调，其实queenCol[curRow] = -1这句话删掉不删掉都是正确的，因为不影响原来调用的函数中queenCol的结果。

class Solution {

public:

    int totalNQueens(int n) {

        if(n <= )

            return ;

        vector<int> queenCol(n,-);

        int result = ;

        int curRow = ;

        totalNQueens(n,queenCol,result,curRow);

        return result;

    }

    void totalNQueens(int n,vector<int> queenCol,int& result,int curRow){

        if(curRow == n){

            result++;

            return;

        }

        for(int i = ;i < n;i++){

            if(isValid(queenCol,curRow,i)){

                queenCol[curRow] = i;

                totalNQueens(n,queenCol,result,curRow+);

                //queenCol[curRow] = -1;

            }

        }

    }

    bool isValid(vector<int>& queenCol,int row,int col){

        for(int i = ;i < row;i++){

            if(queenCol[i] == col || abs(row - i) == abs(col - queenCol[i]))

                return false;

        }

        return true;

    }

};

巴特西

leetcode 51. N-Queens 、52. N-Queens II

最新文章

热门文章