【LeetCode】52. N-Queens II（位运算）

【题意】

输出N皇后问题的解法个数。

【题解】

解法一：传统dfs回溯，模拟Q放置的位置即可，应该不难，虽然能通过，但是时间复杂度很高。

解法二：位运算大法好！

首先要明白这道题里两个核心的位运算

1、x & -x 代表除最后一位 1 保留，其它位全部为 0（这个是不是很熟悉，就是树状数组的lowbit哦）

这里要明白计算机存储数的时候存储的是补码，假设x为0101000，正数的补码还是正数，-x为1101000，其补码为1011000，然后0101000 & 1011000，就是保留x的最后一位1。

2、x & (x - 1) 代表将最后一位 1 变成 0

如果x的最后一位是1，那么x-1后最后一位为0，其他位与x相同，所以相与后就将x的最后一位1变为0了。

如果x的最后一位是0，那么x-1后最后一位位1，且要向x的最后一位1借位，所以最后一位1处变为0，最后一位1 处前面位与x相同，所以相与后最后一位1变为0。这么说可能有点抽象，举个栗子，假设x为0101000，那么x-1为0100111，所以相与就是最后一位1变为0啦。

col、lx、rx代表每一行哪些位置可以放Q，0代表可以放，1代表不能放（col是列，lx是往左倾斜的斜线，rx是往右倾斜的斜线）

所以(t | lx) << 1，(t | rx) >> 1就不难理解了，比如t｜lx 为00100，那么 << 1就是01000，是不是还蛮形象的

【代码】

 1 class Solution {

 2 public:

 3     int ans = 0;

 4     void dfs(int row, int col, int lx, int rx, int n){

 5         if (row >= n){

 6             ans++;

 7             return;

 8         }

 9         // q为该行能够放Q的位置

10         int q = ~(col | lx | rx) & ((1 << n) - 1);

11         while(q){

12             // 取出q的最后一位1

13             int t = q & (-q);

14             dfs(row + 1, t | col, (t | lx) << 1, (t | rx) >> 1, n);

15             // 将最后一位1变为0

16             q = q & (q - 1);

17         }

18     }

19     int totalNQueens(int n) {

20         dfs(0, 0, 0, 0, n);

21         return ans;

22     }

23 };

巴特西

【LeetCode】52. N-Queens II（位运算）

最新文章

热门文章