287. Find the Duplicate Number hard

http://www.cnblogs.com/grandyang/p/4843654.html

51. N-Queens

http://blog.csdn.net/linhuanmars/article/details/20667175 http://www.cnblogs.com/grandyang/p/4377782.html

思路就是利用一个pos[row]=col来记录行号：row，Queen在第col列。

再用一个index来记录当前递归到行号：index。

另外检查时候，只需要传入pos数组跟当前的位置 row，col。并且只需要从第0行倒第row-1行即可。

其中，判断当前行是不需要的，判断当前列跟斜线即可。斜线上直接利用斜率即可：(y2-y1)/(x2-x1)=正负1即可！

不过helper函数中第一个if语句没有 return竟然也能得到正确答案！我已惊呆！

class Solution {

public:

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

        vector<int> pos(n,-);

        helper(res,,pos,n);

        return res;

    }

    void helper(vector<vector<string>>& res,int index,vector<int>& pos,int len){

        if(index==len){

            vector<string> temp(len,string(len,'.'));

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

                temp[i][pos[i]]='Q';

            }

            res.push_back(temp);

        }

        for(int col=;col<len;col++){

            if(isCheck(pos,index,col)){

                pos[index]=col;

                helper(res,index+,pos,len);

                pos[index]=-;

            }

        }

    }

    bool isCheck(const vector<int>& pos,int row,int col){

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

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

                return false;

        return true;

    }

private:

    vector<vector<string>> res;

};

巴特西

287. Find the Duplicate Number hard

最新文章

热门文章