Cinte's Leetcode Record
0%

面试题 08.12. 八皇后

Posted on Edited on In Disqus:
Symbols count in article: 3.8k Reading time ≈ 3 mins.

面试题 08.12. 八皇后

BackTrack
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> ret;
        vector<int> pos(n);
        vector<string> tmp;
        // 从最后一行往前走
        backTrack(ret, pos, n - 1, n, tmp);
        return ret;
    }
private:
    void backTrack(vector<vector<string>>& ret, vector<int>& pos, int curLine, int n, vector<string>& tmp)
    {
        // 如果所有行都走完了，就push入结果
        if(curLine < 0)
        {
            ret.push_back(tmp); 
            return;
        }
        vector<int> avl(n, 0); // 记录已经被占用的位置
        // 遍历之前行，获取到不能放置的位置
        for(int i = n - 1; i > curLine; --i)
        {
            avl[pos[i]] = 1;
            int diff = i - curLine;
            if(pos[i] - diff >= 0)
                avl[pos[i] - diff] = 1;
            if(pos[i] + diff < n)
                avl[pos[i] + diff] = 1;
        }
        for(int i = 0; i < n; ++i)
        {
            if(avl[i]) // 如果位置被占用了，就跳过
                continue;
            pos[curLine] = i;
            tmp.push_back(getLine(i, n));
            backTrack(ret, pos, curLine - 1, n, tmp); // 进入下一行
            tmp.pop_back();
        }
        return;
    }
    string getLine(int pos, int n)
    {
        string line;
        int j = 0;
        for(j; j < pos; ++j)
            line += ".";
        line += "Q";
        while(++j < n)
            line += ".";
        return line;
    }
};
Solution

以上对于已经占用的位置需要消耗掉O(n)的时间复杂度，但是可以观察到

同一条斜线上的行和列之差或之和相等且独一无二，因此只需要记录之差和之和即可判断是否在同一斜线，时间复杂度降为O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> ret;
        vector<int> pos(n);
        col = vector<int>(n, 0);
        backTrack(ret, pos, n - 1, n);
        return ret;
    }
private:
    vector<int> col;
    unordered_set<int> lx;
    unordered_set<int> rx;
    void backTrack(vector<vector<string>>& ret, vector<int>& pos, int curLine, int n)
    {
        if(curLine < 0)
        {
            ret.push_back(getBoard(pos, n));
            return;
        }
        for(int i = 0; i < n; ++i)
        {
            if(col[i] || lx.find(i - curLine) != lx.end() || rx.find(i + curLine) != rx.end())
                continue;
            pos[curLine] = i;
            col[i] = 1;
            lx.insert(i - curLine); // 记录向左上方的斜线，斜线上行列之差相等
            rx.insert(i + curLine); // 记录向右上方的斜线，斜线上行列之和相等
            backTrack(ret, pos, curLine - 1, n);
            col[i] = 0;
            lx.erase(i - curLine);
            rx.erase(i + curLine);
        }
        return;
    }
    vector<string> getBoard(vector<int> pos, int n)
    {
        vector<string> ret;
        for(auto& p : pos)
            ret.push_back(getLine(p, n));
        return ret;
    }
    string getLine(int pos, int n)
    {
        string line;
        int j = 0;
        for(j; j < pos; ++j)
            line += ".";
        line += "Q";
        while(++j < n)
            line += ".";
        return line;
    }
};

T(n) : O(n!)

S(n) : O(n)

使用位运算优化S(n)为O(1)

左边斜线就是上几行皇后位置左移行之差次，右边斜线就是上几行皇后位置右移行之差次。

对于每行，获得左斜线就是左边值左移，右斜线就是右边值右移。即可

具体看解析

x & (x - 1)将最低位1置0

x & -x就是最低位1的位置

二进制中相反数就是按位取反再加一，也就是说 x & -x = x & (~x + 1)，显然可以运算后只有最低位1可以保持1，其他都是0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> ret;
        vector<int> pos(n);
        backTrack(ret, pos, n - 1, n, 0, 0, 0);
        return ret;
    }
private:
    void backTrack(vector<vector<string>>& ret, vector<int>& pos, int curLine, int n, int col, int lx, int rx)
    {
        if(curLine < 0)
        {
            ret.push_back(getBoard(pos, n));
            return;
        }
        auto alP = ((1 << n) - 1) & (~(col | lx | rx)); // 1表示有空位，为了下面的循环方便
        while(alP)
        {
            int lastZero = alP & (~alP + 1);
            int po = __builtin_ctz(lastZero); // gcc __buildin__函数，获取末尾0的数量，这里不能获取前导0，因为前导0会根据int为32位计算
            alP &= alP - 1; // 去除最后一个1，继续
            pos[curLine] = n - po - 1;
            backTrack(ret, pos, curLine - 1, n, col | lastZero, (lx | lastZero) << 1, (rx | lastZero) >> 1);
        }
        return;
    }
    vector<string> getBoard(vector<int> pos, int n)
    {
        vector<string> ret;
        for(auto& p : pos)
            ret.push_back(getLine(p, n));
        return ret;
    }
    string getLine(int pos, int n)
    {
        string line;
        int j = 0;
        for(j; j < pos; ++j)
            line += ".";
        line += "Q";
        while(++j < n)
            line += ".";
        return line;
    }
};

T(n) : O(n!)

S(n) : O(1)