0052._N-Queens_II.md

52. N-Queens II

难度:Hard

刷题内容

原题连接

• https://leetcode.com/problems/n-queens-ii/

内容描述

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.



Given an integer n, return the number of distinct solutions to the n-queens puzzle.

Example:

Input: 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown below.
[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

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

思路1 - 时间复杂度: O(2^n)- 空间复杂度: O(n)******

这题和上一道题基本一样，只是求次数。稍微改动一下就好，具体的不多说了

class Solution {
public:
    int travel(int* d,int level,int n,int* l,int* r)
    {
        if(level >= n)
            return 1;
        int ans = 0;
        for(int i = 0;i < n;++i)
            if(!d[i] && !r[level + i] && !l[i - level + n])
            {
                d[i] = 1;
                r[level + i] = 1;
                l[i- level + n] = 1;
                ans += travel(d,level + 1,n,l,r);
                d[i] = 0;
                r[level + i] = 0;
                l[i- level + n] = 0;
            }
        return ans;
    }
    int totalNQueens(int n) {
        int d[n];
        int l[2 * n];
        int r[2 * n];
        memset(d,0,sizeof(d));
        memset(l,0,sizeof(l));
        memset(r,0,sizeof(r));
        int ans = 0;
        for(int i = 0;i < n;++i)
        {
            d[i] = 1;
            r[i] = 1;
            l[i + n] = 1;
            ans += travel(d,1,n,l,r);
            d[i] = 0;
            r[i] = 0;
            l[i + n] = 0;
        }
        return ans;
    }
};