leetcode N-QueensII

题目和上一题一样，就是要求输出有多少种结果。最直接的就是，只要在上一题的代码return ans.size();就可以了。果然也是AC了。

然后我翻看了几种别人写的，暂时还没有找到复杂度可以比上一题降低多少的。

可以加一个全局变量。以前都没有想到给solution类加全局变量。满足条件的时候全局变量加一。随后返回全局变量就好了。

class Solution {
    int ansT = 0;
public:
    int totalNQueens(int n) {    vector<vector<string> > ans;
    //ans.clear();
    int perm[n];
    //memset(perm, 0, sizeof(perm));
    solve50(perm, 0, n, ans);
    return ansT;  
    }

void solve50(int perm[], int row, int n, vector<vector<string> > &ans)
{
    if (row == n) // 因为row从0开始，说明已经有0到n-1总共n个符合了
    {
        ansT++;
        return;
    }
    else
    {
        for (int col = 0; col < n; ++col)//对与第row行的每一个列，进行判断是否符合
        {
            bool flag = true;
            for(int i = 0; i < row; ++i)//对于第row行的每一个列要与之前的每行锁存的王后判断是否冲突
            {
                if (col == perm[i] || col - perm[i] == row - i || col - perm[i] == i - row)
                {// 当前列等于之前的列，或者当前的点和之前的点的斜率为正负1时，为false，否则true进行判断下一行
                    flag = false;
                }
            }
            if (flag)//没有冲突，记录当前列数，进入下一行的递归选择
            {
                perm[row] = col;
                solve50(perm, row + 1, n, ans);
            }
        }
    }
}
};

有空的时候看看这里介绍的据说比较高效一些的方法。